Submission #80867


Source Code Expand

Copy
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

Submission Time
Task D - grepマスター
User eomole
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1561 Byte
Status AC
Exec Time 2674 ms
Memory 54048 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 12
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 01_min.txt, 02_rand_00.txt, 02_rand_01.txt, 02_rand_02.txt, 03_randp_00.txt, 03_randp_01.txt, 03_randp_02.txt, 04_maxrandp_00.txt, 04_maxrandp_01.txt, 04_maxrandp_02.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 461 ms 20156 KB
00_sample_02.txt AC 425 ms 20132 KB
01_min.txt AC 440 ms 20272 KB
02_rand_00.txt AC 1766 ms 46704 KB
02_rand_01.txt AC 2213 ms 51368 KB
02_rand_02.txt AC 1134 ms 45864 KB
03_randp_00.txt AC 1697 ms 47180 KB
03_randp_01.txt AC 2281 ms 48116 KB
03_randp_02.txt AC 2571 ms 49856 KB
04_maxrandp_00.txt AC 2583 ms 54048 KB
04_maxrandp_01.txt AC 2674 ms 53168 KB
04_maxrandp_02.txt AC 2580 ms 50664 KB