Many solutions have time complexity O(Q * D), where D is the number of elements with count>1 in the array i.e. in worst case it would be O(Q * N).
So were the test cases weak?? 
@coolreshab
Subtask-2 can be solved with MO’s offline query algorithm.
What are appropriate solutions to the problem in which there are 10^5 distinct elements, each present twice?
3 Likes
What is the correct complexity and solution to this problem? O(Q * N) can’t be the intended solution.
Yes the test cases were weak, I got to know during the mid of the contest but couldn’t change them because I didnt had permission to do that.
The intended complexity was (n+q) sqrt(n) .
Lets take b as the block size. So there will be x = (n/b) blocks in total. You need to precompute the answers for each pair of blocks in xn time. Now for each query, you just need to find the nearest block pair that fits the query and use that to reach the query. So the total time complexity becomes, xn + qB = n^2/b + qb . On differentiation you can get the optimal block size as sqrt(n). This is the brief explanation but the detailed editorial will be published soon.
3 Likes
Atleast you should have tried to change the constraints stating that (N*D)<10^8.
I liked the problem. Waiting for the Editorial!
But the problem constraints were not intended to be like that ( N*D< 10^8) .
Sorry for the trouble you got because of this 
1 Like
Although my solution was also (n+q)sqrt(n) but it required 5.6 secs for last subtask, so I applied this cheap trick in it, to get AC under 2 sec
1 Like
I was expecting that there would be a segment tree approach to this question. Do you have any logic pertaining to it?
May be you were using a lot of stl and mod operations. One more thing you could have tried to try different block sizes, this also help us a lot in such cases.
Yup, either of them would have worked 
since my Nsqrt(N) was 1 statements and Qsqrt(N) was 7. But what I suffered was on declaring size of 300000 * 549 globally, I got a compilation error of truncation, although reducing it to 300000 * 548, it ran successfully. How could that even happen? ,there has to be something else wrong which I couldn’t figure out