When I was solving the problem 674G — Choosing Ads, I got a TLE on #10 as result. The submission id is 348821830.

I tried to generate a data and run my code on my Ubuntu, and it took 5.80 seconds. (The python code to generate the data is at the end of this blog.)

I was once told that O2 can make the code run faster, so I tried to compile the code with option -O2 (the full command was like g++ ./t.cpp -o ./t -O2), it just took 0.73s. I added #pragma GCC optimize(2) into the code, and then recompiled it without option -O2 (the full command was like g++ ./t.cpp -o ./t), however it took more than 5 seconds. (I used the command /usr/bin/time -v ./t < ./t.in > ./t.out to measure the time.)

As you can see the two ways above has a huge difference.

I'm wondering why this phenomenon happened.

Is there some problem in my code or the way I compile it? or it can just happen on my Ubuntu?

Thanks a lot.

#!/bin/python3

from random import *

n=150000
m=150000
k=20

print(n,m,k)
for _ in range(n):
    print(randint(1,6),end=' ')
print()
for _ in range(m):
    o=randint(1,2)
    l=randint(1,n)
    r=randint(1,n)
    v=randint(1,6)
    if l>r:
        l,r=r,l
    if o==1:
        print(o,l,r,v)
    else:
        print(o,l,r)

When I was testing on my Ubuntu, all tests generated by this code will cause the phenomenon above.

Update

I've put #pragma GCC optimize(2) to the first line, then the time reduced to 3.13 seconds, still far more than -O2.

Update #2

I've passed it. I changed the map and vector to simple arrays like a[150005], which seems to be a good way to improve speed. On the local test, it took just about 0.5 second. But why there was such a huge difference on pragma and -O2?