I am trying to solve the following problem but I am getting ‘java.lang.OutOfMemoryError’
Problem statement:
Suppose we have a plane with dots (with non-negative coordinates). We make three queries:
1)add dot at (x , y)
2)count number of dots in rectangle (0 , 0), (x , y) — where (0 , 0) if down-left corner, (x , y) is up-right corner and sides are parallel to x-axis and y-axis.
total no.of queries is M and the constraint are as follow
0< x,y <=10^9;
0< M <=100000(=10^5);
the solution given in this topcoder tutorial uses tree[max_x][max_y] i.e. tree[10^9][10^9] and surely one will get ‘out of memory’ error.
I have tried to compress the value of x,y (mapping {1,2,3…} to input set) but still it takes 10^5*10^5 which is out of bound.
Plz tell me what is the right way to solve this kind of problem