Giving tle (time limit exceed) in codeforces. Can anyone help?

Question

Link of the question => https://codeforces.com/contest/1324/problem/D
my Solution
https://code.sololearn.com/cohV8kZC6rD9/?ref=app

Answer 1

You can reduce some time by taking fast input output as there are too many test cases https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

your logic to find such number of such pairs after sorting looks correct to me, still I would like if you can provide some comments next time for getting better help from community.

Answer 2

A better approach of finding such pairs after sorting of that difference array would be to take sum of beginning elements(index i) and ending element(index j) if it comes +ve then it means elements at index i, i+1, i+2, ... , j-1 can be paired with j so add (j-i) to result and do same for (j-1)th element now, if comes -ve then then increase i by 1 and do same.
It will save time getting used in finding first +ve element in difference array.

Answer 3

R_C
I think tle coming mainly because of slow input output in java. I am shifting from java to C++ due to that reason only.

Edit: I tried it in codechef, got struck in same test case but same code in C++ worked perfectly.

Answer 4

In order to increase chances of a good answer, you should help us as much as you can.

Instead of just linking your code and the task, write a summary right here.

Tell us what you have tried so far to find your mistake, and in which part of your code you suspect your bug in.

Add comments to tell us how your code works (yeah, we could figure it out, but that takes additional time).

Stuff like that.

The more work you have already done yourself, the more likely it becomes that someone feels like helping you with the rest.

Answer 5

Gaurav Agrawal
But finding +ve in the difference array will be O(n) complexity. Then why it giving tle.

Answer 6

Gaurav Agrawal
I've used BufferedReader. Giving no tle on test case having n=200000 but tle when n=100000. I don't get it.