rumike's blog

Why did the fenwick with correct merge map of nodes give TLE?
By rumike, 2 months ago, In English

I was resolving that data structures problem, 669E - Little Artem and Time Machine using fenwick tree. As you can see in this submission 280626744, each fenwick tree node have a map, that describe the frequency of elements in that moment. During addition, I have carefully merged nodes by merging the node with a map of small size into the other. But I am getting TLE on testcase 6.

Do someone know why the complexity of my solution is not $$$O(n * log(n)^2)$$$, as for $$$O(n * log(n))$$$ for the fenwick and the $$$O(log(n))$$$ for the merging process? Also as I know fenwick tree don't have a big constant factor.

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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I didn't read the task, but most likely your $$$get$$$ is slow because you are directly merging all the maps that can have a lot of values.

Something like

  int get(int x, int t) {
    int v = 0;
    while (x >= 0) {
      v += fenw[x].a[t];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }

  cout << fen.get(ord[t], x) << endl;

should work. Also it would be good to use "\n" instead of endl;

(It does work)

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

    Thanks a lot, got it.

    And for "\n", why is it better than endl?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      endl does a flush every time (which takes a lot of time), which you don't need if the problem is not interactive

      i don't know any resources with full explanation, but you can google them by yourself, cf should have some blogs about it for sure :)

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

    Got again tle on another problem, but I can't get why again. It's a data structures problem 12D - Ball, where I use fenwick tree to resolve, that's my submission is 280780438.

    The weird thing is that is submitted Roms's accepted solution using segment tree as 280774574, but getting tle on the same testcase as him. So do not know if it's years that have passed, or If I can improve my code complexity?

    → Reply