Find The Evil Monsters :
Difficulty Level : Hard
Submissions : 1060
Asked In :
Marks :20
: 19 | : 2
Given an array $$$A$$$ of $$$n$$$ elements representing the monsters and an array $$$B$$$ of $$$q$$$ elements representing the heros.
The $$$i-th$$$ type of monster is represented by $$$A[i][0]$$$, $$$A[i][1]$$$ and $$$A[i][2]$$$ which means a monster of the $$$i-th$$$ type is present at each integer co-ordinate from $$$A[i][0]$$$ to $$$A[i][1]$$$ and having a strength of $$$A[i][2]$$$.
The $$$i-th$$$ type of hero is represented by $$$B[i][0]$$$ and $$$B[i][1]$$$ which means a hero of strength $$$B[i][1]$$$ will appear at the integer point $$$B[i][0]$$$ after $$$i$$$ seconds. When the $$$i-th$$$ hero appears it will destroy each and every monster present at $$$B[i][0]$$$ and having a strength less than $$$B[i][1]$$$.
For each $$$i$$$ you have to determine the number of monsters left after the $$$i-th$$$ hero has completed their task.
The first line of input contains two integers $$$N$$$ $$$(1 \le N \le 10^5)$$$ and $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ — the number of monsters and the number of heroes respectively.
The next $$$n$$$ lines contains $$$3$$$ integers $$$A[i][0], A[i][1], A[i][2]$$$ $$$(1 \le A[i][0] \le A[i][1] \le 10^5; 1 \le A[i][2] \le 10^9)$$$ each describing the monsters.
The next $$$q$$$ lines contains $$$2$$$ integers $$$B[i][0], B[i][1]$$$ $$$(1 \le B[i][0] \le 10^5; 1 \le B[i][1] \le 10^9)$$$ each describing the heroes.
Print $$$q$$$ space separated integers — the $$$i-th$$$ number should be equal to the number of monsters left after the $$$i-th$$$ hero has completed their task.
3 2 1 3 7 2 5 4 4 8 6 3 5 5 8
11 9
4 3 2 5 8 5 8 6 3 6 9 7 10 10 2 7 7 9 7 11
16 15 14
In sample test $$$1$$$, Initially there are $$$12$$$ monsters in total. The first hero will destroy the monster of $$$2nd$$$ type present at coordinate $$$3$$$ having a strength of $$$4$$$. After the first operation there are $$$11$$$ monsters left. The second hero will destroy the monster of $$$2nd$$$ type present at coordinate $$$5$$$ having a strength of $$$4$$$ and the monster of $$$3rd$$$ type present at co-ordinate $$$5$$$ having a strength of $$$6$$$. Hence there are $$$9$$$ monsters left after the second operation.
In sample test $$$2$$$, Initially there are $$$16$$$ monsters in total. The first hero will not destroy even a single monster. The second hero will destroy the monster of $$$2nd$$$ type present at coordinate $$$7$$$ having a strength of $$$6$$$. The third hero will destroy the monster of $$$4th$$$ type present at coordinate $$$7$$$ haying a strength of $$$10$$$.
