pickle_juice2024's blog

By pickle_juice2024, history, 21 month(s) ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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)