Help with TLEs - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I have a question on this question: https://mirror.codeforces.com/problemset/problem/1409/E

I am getting a TLE on test five (or when n hits its maximum value). My code gives the correct answer, given infinite amount of time, I just need help on figuring out why it TLEs.

From my knowledge, all I do is binary search and do a linear scan, so that's about nlgn time. However, when I submit it, it does not run in time, so I suspect that there is something that I am not catching. I've tried for a long time and still could not figure out why my code is TLE-ing.

I hope you guys can help me out

Thanks in advance!

code (in java): https://mirror.codeforces.com/contest/1409/submission/93014244

Code


import java.io.*;
import java.util.*;
public class twoPlatforms {
    static int t;
    static int n, k;
    static int[] x;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        t = Integer.parseInt(in.readLine());
        for (int test = 0; test < t; test++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(in.readLine());
            x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = Integer.parseInt(st.nextToken());
            }
            int[] y = new int[n];
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < n; i++) {
                y[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(x);
            out.println(solve());
        }
        out.close();
    }
    static int solve(){
        int maxLeft = 0;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int r = binSearch(x[i] + k, 1);
            int rLength;
            if(r < 0){
                if(r == -1) {
                    r = -(r + 1);
                }
                else if(r == -n &mdash; 1){
                    r = n &mdash; 1;
                }
                else{
                    r = -(r + 1) &mdash; 1;
                }
            }
            rLength = r &mdash; i + 1;
            int lLength = 0;
            if(i != 0) {
                int l = binSearch(x[i &mdash; 1] &mdash; k, -1);
                if(l < 0){
                    l = -(l + 1);
                }
                lLength = i &mdash; l;
            }
            maxLeft = Math.max(lLength, maxLeft);
            ans = Math.max(ans, maxLeft + rLength);
        }
        return ans;
    }
    static int binSearch(int target, int dir){
        int l = 0, r = n;
        int res = (dir == 1) ? 0 : Integer.MAX_VALUE;
        boolean found = false;
        while(l != r ){
            int m = (l + r)/2;
            if(x[m] < target){
                l = m + 1;
            }
            else if(x[m] > target){
                r = m;
            }
            else{
                found = true;
                res = (dir == 1) ? Math.max(m, res) : Math.min(m, res);
                if(dir == 1){
                    l = m + 1;
                }
                else{
                    r = m;
                }
                if(l < n && l == r && x[l] == target){
                    res = (dir == 1) ? Math.max(l, res) : Math.min(l, res);
                }
            }
        }
        if(found){
            return res;
        }
        else{
            return -(l + 1);
        }
    }
}