TLE codeforces Div 3 725 C problem

1

I think my solutions time complexity is NlogN but it is giving tle please somebody check this solution
problem link

import java.util.*;
import java.lang.*;
import java.io.*;
public class Codechef {
	public static void main(String[] args) throws java.lang.Exception {
		FastReader in = new FastReader(System.in);
		StringBuilder sb = new StringBuilder();
		int t = 1;
		t = in.nextInt();
		while (t > 0) {
			--t;
			int n = in.nextInt();
			long l = in.nextInt();
		    long r = in.nextInt();
			long arr[] = new long[n];
			for(int i = 0;i<n;i++)
				arr[i] = in.nextInt();
			Arrays.sort(arr);
			long ans = 0;
			for(int i = 0;i<n;i++)
			{   
				if(i==n-1 || arr[i]+arr[i+1]>r)
					continue;
				long x = binary1(arr,arr[i],l,i+1);
				long y = binary2(arr,arr[i],r,i+1);
				if(x!=-1 && y!=-1)
				{
					ans+=(y-x+1l);
				}
			}
            sb.append(ans+"\n");
		}
		System.out.print(sb);
	}

	static int binary1(long arr[] , long value , long min , int i_1)
	{
		int l = i_1;
		int r = arr.length-1;
		int ans = -1;
		while(l<=r)
		{
			int mid = (l+r)/2;
			if(value+arr[mid]>=min)
			{
				ans = mid;
				r = mid-1;
			}
			else 
				l = mid+1;
		}
		return ans;
	}

	static int binary2(long arr[] , long value , long max , int i_1)
	{
		int l = i_1;
		int r = arr.length-1;
		int ans = -1;
		while(l<=r)
		{
			int mid = (l+r)/2;
			if(value+arr[mid]<=max)
			{
				ans = mid;
				l = mid+1;
			}
			else 
				r = mid-1;
		}
		return ans;
	}
	}

class FastReader {

	byte[] buf = new byte[2048];
	int index, total;
	InputStream in;

	FastReader(InputStream is) {
		in = is;
	}

	int scan() throws IOException {
		if (index >= total) {
			index = 0;
			total = in.read(buf);
			if (total <= 0) {
				return -1;
			}
		}
		return buf[index++];
	}

	String next() throws IOException {
		int c;
		for (c = scan(); c <= 32; c = scan())
			;
		StringBuilder sb = new StringBuilder();
		for (; c > 32; c = scan()) {
			sb.append((char) c);
		}
		return sb.toString();
	}

	String nextLine() throws IOException {
		int c;
		for (c = scan(); c <= 32; c = scan())
			;
		StringBuilder sb = new StringBuilder();
		for (; c != 10 && c != 13; c = scan()) {
			sb.append((char) c);
		}
		return sb.toString();
	}

	char nextChar() throws IOException {
		int c;
		for (c = scan(); c <= 32; c = scan())
			;
		return (char) c;
	}

	int nextInt() throws IOException {
		int c, val = 0;
		for (c = scan(); c <= 32; c = scan())
			;
		boolean neg = c == '-';
		if (c == '-' || c == '+') {
			c = scan();
		}
		for (; c >= '0' && c <= '9'; c = scan()) {
			val = (val << 3) + (val << 1) + (c & 15);
		}
		return neg ? -val : val;
	}

	long nextLong() throws IOException {
		int c;
		long val = 0;
		for (c = scan(); c <= 32; c = scan())
			;
		boolean neg = c == '-';
		if (c == '-' || c == '+') {
			c = scan();
		}
		for (; c >= '0' && c <= '9'; c = scan()) {
			val = (val << 3) + (val << 1) + (c & 15);
		}
		return neg ? -val : val;
	}
}
2

Not sure , Arrays.sort is implemented using quick Sort so it takes O(N * N) in worst .

2 Likes
3

thanks buddy

1 Like
4

You were right Arrays. sort() time complexity in the worst case is O(n^2). I implemented the same code using Collections. sort() it worked in 0.2sec.

1 Like
5

Arrrays.sort() on primitive data types is slow.

You should always perform Arrays.sort on Objects.

Integer arr[] = new Integer[n];
Arrays.sort(arr);

The above should work fine always