| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 2 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 4 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
I came across an issue when solving problem C in today's contest. I was trying to find the distance between two pointers (by subtracting) in a set to determine the number of elements between those two pointers. However, I got an error. Is there a way to find this distance?
Submission (under "if(t == 3)")
use ordered set(policy based set)
That might be a good idea. If I am trying to find elements in range L to R, should I do something like order_of_key(R+1) — order_key(L)? (reminds me of prefix sums)
This correctly gives #of rooks between rows L,R, but that's different than "at least one rook in each row in range [L,R]" which is what the problem asks
However, I am using a set combined with a multiset to ensure that only distinct rooks are stored. (Please check my most recent submission) Therefore, in my case, it can be used to check if the condition is satisfied.
Ah true, my bad
std::distance, works in linear time.
I knew there had to be something! Thank you.
Note that it works in linear time for each call of the function, so if you were to use it in your solution, it still would not pass because the total complexity would be $$$O(n^2)$$$. I'm 99% sure that the implementation for std::distance with not random access iterators just increments the smaller one repeatedly until it reaches the bigger iterator...
Yeah, I tried it and it got TLE on test case 5. But I am sure it will be useful elsewhere!
You can't do this with set. You can use ordered_set which requires some installation. Or if you are first inserting then doing queries, i.e You don't insert anything after you make first query, you can use Coordinate Compression and then use Fenwick Tree/Segment tree