My code was failing WA#3 until I got this case working:
4
3 1 1 1
14
1 1 3  1 2 3  2 2 3  2 4 3  3 4 3  4 4 3  2 3 3
1 1 1  1 2 1  2 2 1  1 4 1  2 4 1  3 4 1  3 3 1
> 11000000111111


Other:


8
0 0 1 1 0 0 1 1
35
1 2 1  1 1 1  1 3 1  2 3 1  1 6 1  2 5 1  5 6 1
5 5 1  6 6 1  3 4 1  3 3 1  4 4 1  4 7 1  4 6 1
5 7 1  1 2 0  1 1 0  1 3 0  2 3 0  1 6 0  2 5 0
5 6 0  5 5 0  6 6 0  3 4 0  3 3 0  4 4 0  4 7 0
4 6 0  5 7 0  1 7 2  1 2 2  1 1 2  3 3 2  5 5 2
> 00111100011111111111111100011100000


9
1 1 9 9 1 9 9 1 1
70
1 9 9
1 9 1
1 9 5
1 1 1  2 2 1  3 3 9  4 4 9  5 5 1  6 6 9  7 7 9  8 8 1  9 9 1
1 1 9  2 2 9  3 3 1  4 4 1  5 5 9  6 6 1  7 7 1  8 8 9  9 9 9
1 2 1  2 3 1  3 4 1  4 5 1  5 6 1  6 7 1  7 8 1  8 9 1
1 2 9  2 3 9  3 4 9  4 5 9  5 6 9  6 7 9  7 8 9  8 9 9
1 3 9  1 4 9  1 5 9  1 6 9  1 7 9  1 8 9  1 9 9
3 4 1  2 4 1  3 5 1  2 5 1
3 4 9  2 4 9  3 5 9  2 5 9
1 1 5  1 2 5  1 3 5  2 2 5  3 3 5  8 9 5  7 9 5  9 9 5  6 6 5
3 3 1  3 4 1  3 5 1  4 5 1  5 5 1  5 6 1  5 7 1  6 7 1  7 7 1
> 1101111111110000000001101101101111110111111101111111000000000001111100


7
1 1 1 3 1 1 1
11
4 4 3  3 4 3  4 5 3  3 5 3  1 3 3  5 8 3  3 3 3  5 5 3
4 4 1  1 7 3  1 7 1
> 11110000011

New tests were added. All accepted solution were rejudged, ~4% of them lost their accepted status

as topic

I used the same code

Store a sorted array [L...R]  in each vertex of your ST,  corresponding to [L;R].

If you decide to use SQRT-decomposition in C++ using std::set you can get TLE on test 13. All you need is to replace set -> unordered_set in your code :) (dont forget about C++11)

Edited by author 06.02.2016 13:30

Edited by author 06.02.2016 13:38

Create an unordered map <int, set <int> > and for each number in the input insert it's index to the corresponding position in the map, then for each query use manipulations with upper_bound in the set.

Looks like O(nlogn + qlogn).

Edited by author 13.08.2015 20:29

So my algo is to have a vector of pairs(value and index),
sort them(used usual <algorithm> sort), and then binary
searched each request - first by value, and if value was
correct, by index.

The program ACed, on G++11 compiler with 0.921 time. when
I removed the inclusion of <cstdlib>, it ACed with
0.859(and same on G++14). But funny thing is, on
Visual C++ 2010, it ACed with 0.593s time, which is
astounding(to me at least) because the difference is
quite noticeable(25% drop).

So I guess if you are getting TLE, it's worth a try
to run it with Visual C++ - you might get a pass this way.

Edited by author 17.01.2015 15:10

Many thanks to author of this task and Oleg Strekalovsky [Vologda SPU] for the hint ( http://acm.timus.ru/forum/thread.aspx?id=22536&upd=634614144741133716 ).
PS. It is very unexpectedly to me that some collection types (e.g. HashMap) take so much memory and CPU time in java :-/

Edited by author 19.04.2013 22:14

Edited by author 19.04.2013 22:14

I'm trying to sovle this task using HashMap<Integer, BigInteger>.
Maximal amount of elements in this HashMap object = 70000.
Unfortunatelly, I'm getting MLE, 0.406s 69360Kb.

Which kind of test data should be created to examine memory consumption of my variant ?
TIA.

search if there are the number in the certain interval, use balanced search tree

if you're writing in c++ - use unordered_map instead of map :)

This test will take my AC program ( http://acm.timus.ru/getsubmit.aspx/4790749.cpp ) to TLE (8 secs) :

70000
1 1 1 1 1 1 ... (70000 times)
70000
1 1 1
1 1 1
1 1 1
1 1 1
...
(70000 times)

Could you please add this also ?

Edited by author 21.02.2013 23:59

This is Test 4

11
1 2 2 1 1 1 2 2 1 2 1
11
1 1 3
1 4 1
2 8 1
10 11 1
1 3 1
2 3 1
3 7 2
4 6 2
5 9 2
11 11 2
10 11 2

Answer is 01111010101

Edited by author 08.02.2013 04:06

You should use a SQRT-decomposition. Let BLOCK = sqrt(N) In kth element of the decomposition you should store hash_set containing numbers from k * BLOCK to (k + 1) * BLOCK.

It's possible to use Interval Tree.. on Every node put Vector or Map or Set....
I don't know why, but when I put map I got TLe on 6-th test, but with vector + Binary search got AC:)

I find it very strange when in QuickSort :

pivot = A[(High+Low) div 2]; will get me AC for both tests

while

pivot = (High+Low) div 2;
....
A[pivot] will give me WA4/WA6 .