Can anyone explain why the following code gets TLE on test case 46? What should I do to get an AC. The problem is a straightforward application of prefix sums.
public static void main(String[] args) {
FastScanner fs = new FastScanner();
int n = fs.nextInt();
long[] A = new long[n];
long[] B = new long[n];
for(int i=0; i<n; ++i){
A[i] = fs.nextLong();
B[i] = A[i];
}
Arrays.sort(B);
for(int i=1; i<n; ++i){
A[i] += A[i-1];
B[i] += B[i-1];
}
int m = fs.nextInt();
while(m-- != 0){
long ans;
int t = fs.nextInt();
int l = fs.nextInt()-1;
int r = fs.nextInt()-1;
if(t == 1){
ans = A[r]- (l-1 < 0 ? 0 : A[l-1]);
}
else{
ans = B[r] - (l-1 < 0 ? 0 : B[l-1]);
}
System.out.println(ans);
}
}
From participating in the Kotlin contest, I think Arrays.sort(B) is the problem because Java uses an algorithm with worst case time complexity O(n^2) and there are test cases that may be achieving this. To fix this either shuffle the array before sorting (i.e. override the sort function), or use Long[] instead of long[].
In the case of Kotlin it was better performance wise to shuffle first because IntArray (equivalent to int[]) performed much faster than Array<Int> (equivalent to Integer[]).
I'm not sure the best approach for Java, but someone definitely does.