| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 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 |
Given an array of size n <= 10^5 initially filed with zeros, answer two types of queries:
1 A B C : Perform the following operation arr[i] = max(arr[i],C) , where i = A (MOD B) and 1 <= i <= n .
2 I : Print value arr[I] .
Constraints : 1 <= A < B <= N and C <= 10^9
1 <= I <= N .
1 <= n , q <= 10^5 .
Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).
No; in fact I'm not sure segtree beats would be especially helpful since we aren't performing range updates here.
This problem can be solved via sqrt decomposition. Pick some K near the square root of N and directly apply all updates with B > K. Then maintain a table storing the highest update so far for all (A, B) with B < K. We can answer queries by computing the best answer for each B < K and comparing to the precomputed answer across all B > K.
Thank you so much for your time .
I am confused, I don't see any range query here, shouldn't this be possible in O(n) without following any DS?
There could be multiple i's satisfying i = A (MOD B)
oh, my bad
can you give the link to the question?
https://open.kattis.com/problems/modulodatastructures
I think that i==A (mod B) is a more clear notation
What's the source for this problem? I'd like to submit it
https://open.kattis.com/problems/modulodatastructures (shared above)
Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).