artie's blog

Segment tree problem
By artie, 10 years ago, translation, In English

I'm trying to solve a problem http://www.e-olimp.com.ua/ru/problems/4483. I'm building a segment tree: every node of tree stores 2 minimal elements of particular segment. Code: http://ideone.com/Kjk0BQ. But it fails with memory limit, most likely because of line 110. Is it possible to optimize every time array creation?

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of keeping 2 int variable, you can keep a boolean (b) and a integer (m). Boolean is the expected answer. The other variable contains the minimal element in its range. As K is fixed, so

tr [v].b = tr [v << 1].b || tr [v << 1 | 1].b ||
          (tr [v << 1].m + tr [v << 1 | 1].m < K);
tr [v].m = min (tr [v << 1].m, tr [v << 1 | 1].m);

Thus you can avoid that line :s

→ Reply