Submission #80867

---

Source Code Expand

import java.util.*;

public class Main {
    private static class Query implements Comparable<Query> {
        final int id, x, y, sum;

        private Query(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.sum = x + y;
        }

        @Override
        public int compareTo(Query o) {
            return sum - o.sum;
        }
    }

    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int all = sc.nextInt();
        final int N = sc.nextInt();
        final int M = sc.nextInt();
        final int[] L = new int[N];
        for (int i = 0; i < N; i++)
            L[i] = sc.nextInt();
        final int f = L[0] - 1;
        final int b = all - L[N - 1];
        final int[] intervals = new int[N - 1];
        for (int i = 0; i < N - 1; i++)
            intervals[i] = L[i + 1] - L[i] - 1;
        Arrays.sort(intervals);

        final Query[] qs = new Query[M];
        for (int i = 0; i < M; i++)
            qs[i] = new Query(i, sc.nextInt(), sc.nextInt());
        Arrays.sort(qs);

        final int[] ans = new int[M];
        for (int i = 0, j = 0, fusion = 0; i < M; i++) {
            while (j < N - 1 && intervals[j] <= qs[i].sum)
                fusion += intervals[j++];
            ans[qs[i].id] = Math.min(f, qs[i].x) + N + qs[i].sum * (N - j - 1) + fusion + Math.min(b, qs[i].y);
        }
        for (final int i : ans)
            System.out.println(i);
    }
}

Submission Info

Judge Result