Hello CodeForces. Offensively that round #383 was rescheduled.
Please help me with this problem.
→ Pay attention
→ Streams
→ Top rated
| # | 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 |
→ Top contributors
| # | 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 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/14/2024 19:58:46 (k1).
Desktop version, switch to mobile version.
Supported by
Removing some room (say we want to remove the K-th room in the current configuration) can be split into two phases — first, we find at which initial index would the K-th room in the current configuration be, say that's index P, and then we say that the room at index P is removed. Obviously, answering a query of type 'L' can be done by just running the first phase of what I explained above.
Now, let's see how we can implement these phases. Suppose that up to now, we know which indices were already removed and we want to find the index of the K-th available room in the current configuration. This can be done using a binary search since this index P is the smallest P, for which P - count(P) ≥ K. Here count(i) is the number of rooms we have already removed, having indices less than or equal to i. Once we have found this index P, we just mark it as removed.
The only question that remains, is how we mark some index as removed and how we find count(i) fast enough. Well, that's pretty much what any BST does, my choice was to use treap. Sorry, I was too lazy to code one so I just copied one of my previous implementations. Here is my accepted code.
You can also find k-th available room with segment tree in log(1e9).
My first submission was a dynamic Fenwick tree, which got MLE. Yours is also close to the limit while my solution is far away from it. That's why I explained the solution with treap. The topmost solution uses your code and the one below it is my own.
P_Nyagolov _index -> Thank you =D