CCOST  Calculate The Cost
In a small village near the Himalayas, there is a rich landowner, in possession of a vast, rectangular tract of land. Unknown to him, a major oil corporation has verified the existence of a vast oil resource beneath his land.
The oil company sends a man to negotiate the purchase of a rectangular field from within the landowner's land, with sides parallel to those of his area. The landowner, valuing his land according to the trees growing in it and the area to be purchased, gives the company man a map of his land, marking the location of trees of different types, and a list of the worth of each type of tree.
To ensure the most economic purchase of land with the required dimensions, the company man provides you with the data in his possession, and along with that, a list of the land areas that he considers good by his judgement.
You must provide, for each land area that he has listed, the sum total of the values of the trees that lie within or on the boundary of that land area.
Input
The first line of the input contains an integer T, which is the number of test cases. For each test case, the first line contains an integer n, equal to the number of trees in the area. This line is followed by n lines each containing three integers separated by spaces which are the coordinate of the tree (x, y) and value of that tree. Following this is an integer R, equal to the number of proposals of land areas given by the company man. Next R lines contain 4 integers each (x1, y1, x2, y2) which are the coordinates of lower left (x1, y1) and upper right (x2, y2) corner of the rectangular area.
Output
For each test case, your program should output R lines containing the sum of values of the trees which lie inside or on the corresponding rectangular plot. There should NOT BE any blank lines between output of different test cases.
Example
Input: 1 3 1 1 2 2 2 3 3 3 4 2 1 1 1 2 0 0 5 5 Output: 2 9
Constraints
T ≤ 10, n ≤ 10^{5}, r ≤ 50000, 0 ≤ x, y ≤ 10^{7}, value of any tree ≤ 10^{4}.
For any rectangular area 0 ≤ x1 ≤ x2 ≤ 10^{7}, 0 ≤ y1 ≤ y2 ≤ 10^{7}
Note 1: There can be more than one tree at the same point.
Note 2: The input data is large (about 15 MB), be careful about your input and output routines.
hide comments
tien0903:
20181221 10:29:19
nai xừ :D 

Phạm Bãng Ðãng:
20160818 16:00:37
NICE problem :))))


Himanshu:
20160809 17:44:29
can be solved with just 1DBIT. 

anando_du:
20150727 11:30:04
nice problem ^_^ inclusion exclusion caused me some WA .. and Array Limit caused RTE for 7 times _ finally AC ^_^ 

Rishav Goyal:
20140109 22:01:36
i think nlogn+rlog^n should pass the time limit. NO? 

aristofanis:
20130523 14:46:50
int => WA

Added by:  Ajay Somani 
Date:  20080205 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  CodeCraft 08, Problem Setter: Ajay Somani,Anshuman Singh 