ontheqt's blog

By ontheqt, history, 2 months ago, In English,

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);
        }
    }

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it