I am currently stuck on this problem: https://codeforces.me/contest/296/problem/C Any help would be appreciated. PS: I couldn't understand the editorial
# | 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 | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I am currently stuck on this problem: https://codeforces.me/contest/296/problem/C Any help would be appreciated. PS: I couldn't understand the editorial
Name |
---|
Hint: If you know how to do queries of incrementing a range where size of array is n(<=100000) and no. of queries q (<=100000) in O(n+q) then u can solve this problem by applying the technique twice. If you dont know the above technique: https://www.youtube.com/watch?v=4AFWuZIbJ9g&ab_channel=HimanshuSingal
So the idea to do this problem is you can merge multiple queries of the same type into one query. For example, the query 1 5 3 repeat 5 times is equal to 1 5 15. Then you can just using range queries technique to calculate the number of times each query is used, and then another time to execute the queries to the array. The time complexity is O(n+q) or O(n log n + q log q) depend on the range queries algorithm you used (segment tree, BIT, difference array, or stuff like that)