Vectors make solution TLE?

Правка en1, от Filikec, 2024-11-11 18:37:57

In the latest contest I solved 2028C - Alice's Adventures in Cutting Cake in ~ O(nlog(n)). My first submission got TLE, which I found odd so I optimized it — tighter bound for BS and static array used for DP, which passed in 200ms.

Then I started adjusting my original solution and found out that if I use C++23 (GCC 14-64, msys2) instead of C++20 (GCC 13-64), the solution passes. If I create a single static vector, the solution is much faster.

C++23 (GCC 14-64, msys2): 291080726 — ~ 1400ms

C++20 (GCC 13-64): 291080768 — TLE

Single static vector: 291080651 — ~ 300ms

I have two questions:

1) Does anyone know why the compiler version changes the runtime so dramatically and how to prevent it?

2) Since creation of a vector is linear in its size, why is the runtime increased so much?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Filikec 2024-11-11 18:37:57 876 Initial revision (published)