Блог пользователя rumike

Why did the fenwick with correct merge map of nodes give TLE?
Автор rumike, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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)

→ Ответить