All submissions for this problem are available.
King Napoleon wants to protect his kingdom from external attack. For this purpose Napoleon decides to place N surveillance centers in his kingdom. Every surveillance centre takes care of a region in his kingdom. After placing N surveillance centres king wants to know the strength of K vulnerable places in his kingdom. Strength of a place is the number of surveillance centers covering this point. The region of a surveillance centre is described by a rectangle having sides parallel to X and Y axes . A centre is said to cover a place P(x,y) if P lies inside or on the boundary of its region.
Input begins with a line containing an integer T . Then T testcases follows. First line of each testcase contains two integers , N and K which denote the number of surveillance centres and the number of vulnerable places respectively. Each of the next N lines contains the description of a surveillance centre using four integers x1,y1,x2,y2,where (x1,y1) and (x2,y2) are lower left and upper right coordinates of the rectangular area under the centre. The next K lines each containing two integers x,y describe the coordinates of vulnerable places.
For all test cases output the strength of each vulnerable place in the same order as given in the input.
1 <= T <= 10
1 <= N,K <= 100000
1 <= x1,y1,x2,y2,x,y <= 100000
Input: 2 1 1 1 1 4 4 3 3 2 2 1 1 4 4 2 2 5 5 6 6 3 3 Output: 1 0 2
|Time Limit:||0.101911 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.