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

Why am i getting TLE?
Автор im_115, история, 3 года назад, По-английски

Problem link — 1354D - Мультимножество
Solution link — 143561353

I am using segment tree. The time complexity of the code is O( n * ( (logN)^2 ) ) which should pass the time limit. I am also using ios_base::sync_with_stdio(0);cin.tie(0); for fast IO.

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

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

The time complexity of the code is O( n * ( (logN)^2 ) ) which should pass the time limit

It should not pass the time limit. For $$$n =10^6$$$, $$$n *(logN)^2 = 4*10^8$$$. This should only pass only if the solution was some dp with simple recurrence like multiplying a couple of other dps, not for a high constant algorithm like segtree, and even then it would probably be tight on this 1.5 second time limit.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is Fenwick tree faster than segment tree?
    Also i am using a class for segment tree. So does using a class makes the program slow?

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The complexity sounds right, but a segment tree has a relatively high overhead that won't make it work in this case. You can use the same algorithm with a Fenwick tree, which has the same complexity as a segment tree but uses less memory and is faster. For reference: my solution

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is Fenwick tree faster than segment tree?
    Also i am using a class for segment tree. So does using a class makes the program slow?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      No, classes don't necessarily make your program slower. In fact, in my solution I'm using a class for my Fenwick (well, a struct, but it's just a class with default public access).

      A Fenwick is definitely faster than a segment tree (look at how simple the update and query operations are), but it's not as versatile. In particular, you can only do range queries if the operation you're using is invertible — so a sum is ok, but a maximum is not. In the restricted case of only querying for a prefix, you can also do maximum queries, but you loose the ability to query arbitrary ranges.

      Additionally, a fenwick also uses less memory than a segment tree (fenwick N+1 items, segment ~2N)

      → Ответить