sajidali6567's blog

CSES: Salary Queries Solution using Dynamic Segment Tree
By sajidali6567, history, 13 months ago, In English

Hi everyone,

I am trying to solve salary queries from CSES using Dynamic Segment Tree. But I am getting TLE.

My understanding of time complexity is: get and update query is log(O(max_value)) which is log(10^9) = 30. There could be 2 * 10^5 queries, and 2 update is done in case of update. so total is 2 * 10^5 * 30 * 2 = 12 * 10^6 and update query is run on input array elements 30 * 2 * 10^5 = 6 * 10^6 so total Complexity is 3 *(6 * 10^6) = 1.8 * 10^7

Problem Link: https://cses.fi/problemset/task/1144 Code Link: https://ideone.com/QfRtXB

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know dynamic segment tree but this problem can be solved with a normal segment tree

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah

    though, you have to do it offline and do some mapping/compression to get it right

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It can be solved online with the solution mentioned in this Blog

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right not_ahmed_hamed, I am referring the same blog primarily. but it uses index compression. Dynamic Segment Tree is another way to solve the problem. You can refer to my implementation for the same.

        → Reply