orz's blog

By orz, history, 8 months ago, In English
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

approach for f with euler tour and lazy Propagation with seg tree is giving tle on tc 22. here is the code- https://mirror.codeforces.com/contest/1891/submission/230589277

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Fenwick tree is much faster than a regural segment tree, and segment tree without lazy propagation can me much faster than the one with lazy propagation. Also the up-to-bottom implementation of segment tree can be substantially slower than the bottom-to-top one.

    Also note that in your implementation of Euler tour each vertex is put twice in the array. This is not needed, however: one time (either at the beginning or at the end of the dfs procedure) is enough.

    So I definitely feel for you, but I have to admit there is enough room for optimization in your solution. My approach gets OK in 295 ms: 230557194. If I were a problemsetter, I would try to loosen TL as much as possible, and your solution would probably get OK as well.

    P.S. The editorial proposes the same approach I used.

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

      thanks for this knowledge.I don't know how to use fenwick tree,i will try to learn in few days. I know i can optimize my code further and my changing map to unordered_map i got ac.