All submissions for this problem are available.
Mark,a magician, has a great interest in arranging sticks. He use to play with various sticks of different lengths. He put n sticks on the table along one axis, going from left to right. Every stick stands perpendicular to that axis so that the axis passes through the center of its base. The i-th stick has the coordinate xi and the length li. Now Mark wants to learn for every stick, how many sticks will fall if he pushes it to the right. Help him in finding that.
Consider that a stick falls if it is touched strictly above the base. In other words, the fall of the stick with the initial coordinate x and height h leads to the fall of all sticks on the segment [x + 1, x + h - 1].
The first line contains the number of test cases(1<= T <=10). The next line contains integer n (1 ≤ n ≤ 10^5) which is the number of sticks. Then follow n lines containing two integers xi and li ( - 10^8 ≤ xi ≤ 10^8, 2 ≤ li ≤ 10^8) each, which are the coordinate and height of every stick. No two sticks stand on one point.
Print n space-separated numbers zi — the number of sticks that will fall if Mark pushes the i-th stick to the right (including the stick itself).
Input 1 4 16 5 20 5 10 10 18 2 Output 3 1 4 1 Input 1 4 0 10 1 5 9 10 15 10 Output 4 1 2 1
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.