AnotherRound's blog

Help with TLE on CF 355 problem D
By AnotherRound, history, 9 years ago, In English

After reading the solution to problem D from last CF round, I decided to implement it(the idea with 2D segment tree). I know that there are other(faster) ways to implement segment tree as needed for RMQ, but I wanted to implement it with standard(check my code for what I call standard) implementation of 2D seg tree. Unfortunately, I got TL on test 16. So I wanted to ask whether there is some way to optimise my solution(without using the other faster way to implement segment tree). Link to my code: http://mirror.codeforces.com/contest/677/submission/18295468

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This is actually not a 2D segment tree. This is a quad tree which has worst case complexity O(N) per query (in your case it can become O(N*M) per operation). Try implementing it using a 2D Fenwick tree or like you said 2D segment tree (not Quad tree).

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

    Do you have a link to a good implementation of real 2d segment tree? I couldn't find it on google(at least none were god enough)?

    → Reply