This time, Auroraa_ is solving 524E - Ладьи и прямоугольники. After some trial, he got
and then received TLE: 260160406
He was surprised, so he tried it again with exact same code, with C++17 (32). You know what? The AC magic happened again: 260161644.
At first glance, we do think some code has triggered undefined behaviours like Access out of bounds. But Auroraa_ denied that, because all the data could be fit in int32_t.
Then came the dramatic scene: by simply changing the code vector<int>v1[N], v2[N];
to vector<long long>v1[N], v2[N];
, the strange TLE problem disappeared: 260164936.
After that, my further investigation[submission:260199113] pointed out that the block causes TLE is:
for (int i = 1; i <= q; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
vec.push_back({ x1, y1, x2, y2, i });
}
It took over 2000ms(260199205) to write data into this vector. And only took about 100ms(260199447) to do the same thing if we just changed vector<int>v1[N], v2[N];
to vector<long long>v1[N], v2[N];
. The weirdest thing is, there is no direct connection between v1,v2 and vec.
Have you read this blog?