wck_iipi's blog

By wck_iipi, history, 2 hours ago, In English

I was doing the following question: https://codeforces.net/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://codeforces.net/contest/2044/submission/304178376

Spoiler

However, the official solution is in O(n^2) time, which is about (4 * 10^10 operations). https://codeforces.net/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
  • 0
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it
FOR(i, 1, N) {
    FOR(j, 1, N) {
        if(i * j > N) break;

It is $$$O(n \log n)$$$

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you I missed that.