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?

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 x*n 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, x*n + q*B = n^2/b + q*b . 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.

**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

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

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