Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

wck_iipi's blog

By wck_iipi, history, 6 weeks ago, In English

I was doing the following question: https://mirror.codeforces.com/contest/2044/problem/F

Upon doing this question, I used a method that gives the solution in O(nq) time (about 2 * 10^5 * 5 * 10^4 = 10^10 operations). Code is as follows:

https://mirror.codeforces.com/contest/2044/submission/304178376

Spoiler

However, the official solution is in O(n^2) time, which is about (4 * 10^10 operations). https://mirror.codeforces.com/blog/entry/137306

Spoiler

My solution, however gives TLE. Why is my solution giving TLE but official is not even though operations are lower?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
FOR(i, 1, N) {
    FOR(j, 1, N) {
        if(i * j > N) break;

It is O(nlogn)