I tried to implement the problem using segment tree and multisets. I got a verdict of TLE. How can I optimize my code? Or is there a better solution?
Problem link: http://www.spoj.com/problems/KQUERY2/en/
Solution link: http://ideone.com/gDAmUW
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
I tried to implement the problem using segment tree and multisets. I got a verdict of TLE. How can I optimize my code? Or is there a better solution?
Problem link: http://www.spoj.com/problems/KQUERY2/en/
Solution link: http://ideone.com/gDAmUW
Name |
---|
Both N and A[i] are quite small, so maybe something like sqrt decomposition with fenwick tree in each block would pass.
It seems that u will get ~1000 operations for each query with this approach. Idk, mb 2 * 10^8 will pass in 0.85s on spoj
You can try using an array instead of the multiset to get O(log^2 N) complexity per query.
Depending on how the multiset is implemented you will get extra O(log N) factor of a big constant.
If I use an array will it not cause me a MLE? I mean I need to create a 2D one. Or am I not getting your idea? If it's not too much of a trouble can you please elaborate a bit?
i believe he ment to do following: in each node of ur seg.tree store sorted array of elements of its subtree instead of multiset. This doesnt work anyway i believe.
If u use array instead of multiset u'll get like O(nlog^2(n)) rep update query, wont u? i mean u'll have to resort arrays all the time.
Oh, I haven't seen the modify operation but the query one.
your approach is incorrect
this works in
O(n)
I actually wanted to get the index which structures like vectors allow. Is there any way I can fix it? And does that help me to get an AC?
If you want a datastructure that allows you to get the index of the element in O(log(n)) you should either implement something like a treap or use PBDS ( http://codeforces.net/blog/entry/11080 )
I think u should use 2-D BIT
Lol the memory limits are so lenient that you don't even need maps — you can literally just do
and still have over half the memory to spare
You can find the solution here: http://codeforces.net/blog/entry/18470