When I was solving the problem 674G — Choosing Ads, I get 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 takes 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 is like g++ ./t.cpp -o ./t -O2), it just takes 0.73s. I added #pragma GCC optimize(2) in the code, and then recompile it without option -O2 (the full command is like g++ ./t.cpp -o ./t), however it takes 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 happened on my Ubuntu?

Thanks.

#!/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)