naivedyam's blog

Why a TLE in O(n + mlogn) even though n <= 2e5, m <= 2e5?
By naivedyam, 2 weeks ago, In English

My solution to B — Cryptography gives a TLE on test case 13 even though (I feel) my solution meets the constraints. I am building the segment tree in O(n) and answering m queries in O(mlogn). So even in the worst case my solution should run in < 4e6 operations right? Then why a TLE?

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

»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Don't use vector<vector> for 2x2 matrices. int [2][2] are way faster. Initializing vectors of vectors a lot of times might be the reason for the TLE.

My code is similar to yours.

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

    Your code isn't visible to me clicking on it says "You are not allowed to view this page." But I got the point. However, how would we know in what situation it will give TLE and when it won't? Because in this case the number of Operations is < 4e6 which is way off from the 1e8 limit so this isn't even a close TLE situation. In other words how slow is a vector<vector> from an int [][]?

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

      I was told that whenever you need to initialize a lot of small vectors, it's better to use arrays instead. In this case, whenever you have a segment tree with matrices as nodes (fixed size matrix), use arrays. Alternatively, you could use std::basic_string (Kudos to defnotmee for teaching me about it), which works like a vector but is specially optimized for initializations with small size.

      Nonetheless, it is surprising to me that the TLE happened in this situation. In the future, if you notice a TLE when using lots of vector, I would suggest being suspicious of it.

      → Reply