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

Why a TLE in O(n + mlogn) even though n <= 2e5, m <= 2e5?
Автор naivedyam, 2 недели назад, По-английски

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?

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

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

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.

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

    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 [][]?

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

      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.

      → Ответить