im_115's blog

Why am i getting TLE?
By im_115, history, 3 years ago, In English

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.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

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

    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?

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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)

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

        Ok thanks.

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

          Extra credit: not needed in this case, but you can solve the problem quite elegantly in O(NlogN) by doing the search directly "inside" of the fenwick tree, as explained here.

          (see: my solution)

          → Reply