Today I am doing 1107G, I find there is something wrong with my st-table, so I change the st-table into brute force and submit it only to check if my main algorithm is correct.

But to my surprise, the brute force got an "Accepted" verdict in "233ms".(the time limit is 3.5s) https://mirror.codeforces.com/contest/1107/submission/180935577

I am very confused and check the time complexity of my code.

Then I find that:

The st-table code is $$$O(n\log n)$$$.

If I change the '<=' on the 61-th line into <,it's also right thought it seems to be $$$O(n^2)$$$. Because under the constraint of $$$d_{i}<d_{i+1}$$$, it's impossible to construct a testcase with more than 40000 positions with a increasing $$$(d_{i}-d_{i+1})^2$$$.(if the limit of $$$d_i$$$ is $$$10^{18}$$$,it will be TLE as well.

But the original code is totally wrong. It will be TLE on a test constructed in this way:

int cur=100;
cout<<300000<<" "<<300000<<endl;
cout<<1<<" "<<100000<<endl;
rp(i,299999)cout<<cur+i<<" "<<1<<endl;

It takes around 25s for the original code to run, much more than 3.5s.

The Custom Invocation of Codeforces can input only 255KB test, so I test it another OJ(luogu).You can take a look at https://www.luogu.com.cn/problem/U261730 and submit #180935577 into it to see if it has a correct complexity.

And all the correct codes runs well on the only Hacking data.

I know Codeforces has very good testing computer, but it can't change 25s into 3.5s.(If it can...)

I don't know what to do to hack or add testcases to a 5-year-ago edu contest.

I also don't know how many people got "Accepted" in this problem with totally wrong code.(maybe only me?)

If there's some ways to submit hacks or add testcases, please tell me.

If it is unnessesary in Codeforces rules, please ignore this blog or tell me under the blog.

And please tolerate my poor English :)