BGSHOOT  Shoot and kill
The problem is about Mr.BG who is a great hunter. Today he has gone to a dense forest for hunting and killing animals.
Sadly, he has only one bullet in his gun. He wants to kill as many animals as possible with only one bullet.
He has already known the information of duration availability of all animals of the forest.
So, he is planning to shoot at a time so that he could kill maximum animal.
Input
Input begins with an integer N denoting total numbers of animals.
Next N lines contains the duration of availability of animal denoting by X (Starting time) and Y (Ending time) .
Then, there will be Q, denoting the total numbers of queries to be answer.
Each query giving two integer L and R, L denoting the time hunter will come to forest and begins shooting
and R denoting last time upto which he will stay at forest for hunting.
Output
For each query output an integer denoting maximum numbers of animals he could kill by shooting at a time during L and R (inclusive).
Constraints:
1<=N,Q<=100000
1<=X,Y,L,R<=1000000000
Example
Input: 4 1 2 2 3 4 5 6 7 4 1 5 2 3 4 7 5 7 Output: 2 2 1 1
hide comments
gustavoleal:
20190529 03:50:42
path compression and max sparse table solve XD 

losmi247:
20180328 17:28:24
coordinate compression + segtree works just fine, there's no need for lazy, you can just keep track of how many animals are alive at the ith moment Last edit: 20180511 17:30:48 

akt_1998:
20170713 15:54:25
cakewalk ;) 

sharif ullah:
20170602 17:26:17
if u are beginner then need solution??? ha ha!!!!!!!!!! so,first search coordinate compression in google and then take pen and paper then choose DS then solve it 

mycode_123:
20170409 11:34:12
Nice problem....learnt new thing!:) lazy+seg tree+compression


realflash:
20160725 15:01:26
segment tree, lazy propagation,path compression :)


SUBHAM SANGHAI:
20160603 20:24:30
Awesome Problem.. BIT+segment tree+path compression.. Everything in one qstn.. 

suggu:
20160531 08:52:37
1st query  the maximum no. of animal will be killed at time =2 output = 2(1 2 and 2 3)


BISHAL GAUTAM:
20160515 13:15:12
If you had read carefully there is a line "by shooting at a time"....So, question is asking maximum number of segment that could be hit by any one of point from L to R. Hope it helps. 

akshayvenkat:
20160513 19:50:28
is the output correct?

Added by:  BISHAL GAUTAM 
Date:  20160507 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 