hurt_FOR_heart's blog

Need help in problem E — Greedy Shopping
By hurt_FOR_heart, history, 4 years ago, In English

Hello, at problem E last contest I have do segment tree and binary search which reach a good complexity O((n+q)log(maxY)log(n)) but i dont know why It just give me a TLE judgement on test 18 Maybe my poor implementation ? Or there's some infinite loop ? Or I just make a wrong calculation in complexity ? I still cant find my mistake so I hope u guy could help me. Here is my code: https://mirror.codeforces.com/contest/1440/submission/98824111 Thanks in advance.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

I think your type 2 queries might be $$$\mathcal O(\log^2 n \log y)$$$.

while (pos <= n): This while loop executes $$$\log y$$$ times, once for each continuous segment.

first_small(pos,y), Get_pos(pos,y): Both of these seem to be $$$\log^2 n$$$ operations. They each have a $$$\log n$$$ while loop and call Get(1,1,n,pos,m) or Get(1,1,n,m,m) at each iteration, which is another $$$\log n$$$ operation.

To remedy this, replace Get(1,1,n,pos,m) or Get(1,1,n,m,m) by simply checking the sum of the subtrees in $$$\mathcal O(1)$$$ when deciding which children to traverse to.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    i got it,thank you so much for helping me. But i have use some technique called walk on tree. Is it what you mean ?

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

      Yes, I was describing walking down the tree in my last sentence :)

      → Reply