DPR's blog

By DPR, history, 6 weeks ago, In English

PROBLEM : 1538C - Number of Pairs

119286813 -> my submission

119286794 -> some guy's java submission which got accepted

I fail to understand why my submission is failing when is has the exact same logic as the submission which got accepted.

I tried to make it work, but nothing seems to work.

I guess i'll have to say fuck off to java and use C++, because this is just demoralizing.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Arrays.sort() can be n^2 if you make the right test case.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, then why did the second submission get accepted? Both of them used Arrays.sort()

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Arrays.sort() for primitives uses quick sort which is O(n^2) worst case. For array of objects (in this case Long[]), Arrays.sort() uses merge sort which is O(nlogn) worst case.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did kinda similar than u and i got TLE in case 4, then i use FenwickTree and was accepted, you can see my solution here: 119204402