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
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
16:20:56
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
16:20:56
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 01:14:06 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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