My solution is O(cxlog(cx)+cx). Why is it giving TLE on subtask 2? I used co-ordinate compression to lower the co-ordinates to order of c*x and then used sets to traverse the elemets within ranges like [l…r].
My Code
Near the end of your solution, F(i, 1, n + 1) should be F(i, 1, c + 1).
1 Like
Hey all, I tried to implement the idea as per the editorial but I’m getting TLE for almost all cases. Can anyone please help where I’m going wrong?
Here is my code : CodeChef: Practical coding for everyone
oh thanks a lot
bro ur GOD and i m so dumb and I couldnt even debug myself , thanks for being so helpful
Before this problem, I wasn’t about the line sweep technique, every time I think a lot about such intervals.
Now I got the exact thing line sweep.
Here is a nice blog on this How to sweep like a Sir - Codeforces.
Happy coding 
1 Like
Getting WA in subtask 2
https://www.codechef.com/viewsolution/44316180
edit: forgot to add students at the end of the interval to the independent students variable. AC now
It was indeed a good question. Learned a lot. Still solving.
1 Like
I solved this question using dsu, I was hoping to get TLE on this solution CodeChef: Practical coding for everyone
because I got TLE on this:
CodeChef: Practical coding for everyone
The only optimization I did in the first solution is that I am not applying binary search if parent[i]=parent[j] for all i [0,c-1] and all j [i+1,c-1], which should fail for extreme case like c=1000, all x=100 and all intervals have zero intersection.
Number of iterations in worst case scenario - T*(number of elements) * (clubs) * (sum of log(elements in each club))
which comes out to be- 10* 2e5 * 1e3 *7e3 ~ 1e12.
I am using Klee’s algorithm. My solution is passing 70 point sub-task but giving runtime error in sub-task 1. Can any one help with this?