Today I am doing [1107G](https://codeforces.net/contest/1107/problem/G), 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://codeforces.net/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 though 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 on another OJ (luogu). You can take a look at https://www.luogu.com.cn/problem/U261730 and submit [#180935577](https://codeforces.net/contest/1107/submission/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 :)↵
↵
↵
But to my surprise, the brute force got an "Accepted" verdict in "233ms".(the time limit is 3.5s)↵
https://codeforces.net/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 though 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 on another OJ (luogu). You can take a look at https://www.luogu.com.cn/problem/U261730 and submit [#180935577](https://codeforces.net/contest/1107/submission/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 :)↵
↵
