I was trying this problem and got an approach using segment tree lazy as: However, due to x,y being upto $10^9$ I am unable to implement it. I think there's a way of doing this which I am unaware of. It would be of great use if anyone can suggest me how to do this. Thanks :) asked 02 May '18, 23:08

Hi @dishant_18 ! Actually u don't need to use lazy propagation ! It can be done using Merge Sort Tree ! What we actually need is an integer value which completely lies with the given ranges (considering each input as a range) and also that integer value should be as minimum as possible and the number of ranges satisfying this particular value should be as maximum as possible ! So,the how to pick that minimum integer ? We can say that the minimum value will be any one of the starting ranges (i.e among all the ranges pick the starting point of that particular range and count how many ranges satisfy ! ) To do this we need to sort the ranges according to their starting points ! Then iterate through all ranges pick the starting value and count how many ranges satisfy this value ! How to count ?? Build a segment tree with ending point of every range as leaf node and merge two child's to get elements in the parent node ! Then for every query of type "How many numbers are greater than the current number in the range (0,current_index) ?" , to do this we can use lower_bound on each completely overlapping segment and sum them up and return ! Out of all the queries modify the maximum value accordingly along with the minimum value as the current starting point of the range ! My AC code : https://www.hackerearth.com/submission/16653996/ If you have any doubts feel free to ask ! Happy coding :) answered 03 May '18, 00:58

No Need of segment Tree. First Use coordinate compression for X and Y. Now you may observe that after doing this you will have atmost 2*10^5 distinct elements left. Now when you are compressing X and Y , just store this mapping between original number and new mapped value in a map. After you have done this process X and Y values one by one. Suppose current student's mapped range is x=mp[X] and y=mp[Y]. So adding one to a given range can be done by using this simple trick: A[x]+=1 and A[y+1]=1. Here A is the array initialized to 0. Do this range addition for all students. Once you have done this , just take the prefix sum from 1 to 2*10^5(in worst case). Now check all indices from 1 to 2*10^5 and find the smallest index having the maximum value. So simply this is the maximum no. of students that can be made happy and to get the minimum no. of candies just output the map value of the smallest index for which maximum value is encountered. answered 03 May '18, 20:04

answered 03 May '18, 04:35
