With a bit of optimization, my O(NQ) solution (which got TLE in C++ for the second sub task of CHEFEXQ) in PyPy (python) fetched me 100 pts. Can anyone explain the plausible reason behind this ? Were the test cases weak or the TL in PyPy was exceptionally high ?
Here is the LINK to my solution.
The same thing happened to me
Generally the time limit given in pypy is 5 times what they gave in c++.
In C++ it was 3 seconds. For pypy it was 15 seconds. The maximum time taken by any subtask was around 14.75 sec. Little bit more would cost TLE.
I dont know the exact answer why it happened. 15 sec allowed might be the reason, which is much for pypy atleast for this question.
I guess we all should consider switching to PyPy in this case.
I faced the same thing and the maximum time taken by my code was 14.97.
Even in java O(NQ) solution gave 100 points.
This is disappointing for those who used the correct approach(SQRT decomposition) to solve this problem.
Actually sqrt decomposition solution is also getting tle with c++.
However with pypy AC in ~1.5 seconds.
I solved the problem in C++ itself. Didn’t get any TLE.
Here’s my solution
I solved it through square root decomposition method.
Could you share your C++ code?
Most of the part is same.
Except i used map.
Plz if u could see what more optimisation could be done to this code.
I tried faast input also.
If you use sqrt decomposition in C++ using Map , you will get TLE .
Instead , use sqrt decomposition in C++ using normal array with enough space , it will pass . No memory limit exceeded occurs in this case .
My Solution in C++ :Soln
Square root decomposition is the proper method to solve this question. So you will get AC with 100pts. I was talking about the O(NQ) solution which gave TLE in C++ but passed all test cases in PyPy (python).
Link : https://www.codechef.com/viewsolution/16429397
And in python, the brute method will get you 100pts
The same thing happened in previous challenge(NOV Challenge) in question segprod where simple sparse table in pypy got AC ,whereas in C++ that code could not pass a single subtask.
Thats because you are using map (amortized O(logn) insertion and O(logn) look up ) a simple 2d array (O(1) lookup)or unordered_map would give perfect ac …my solution took only 0.57 sec
Can i get the link to that solution (segprod) ?
Sorry!! I did a large no.of submissions for that sum,so its pretty hard to find it
Unordered map also gives tle