AtCoder Regular Contest 014

Submission #80867

Source codeソースコード

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

Task問題 D - grepマスター
User nameユーザ名 eomole
Created time投稿日時
Language言語 Java (OpenJDK 1.7.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 1561 Byte
File nameファイル名
Exec time実行時間 2674 ms
Memory usageメモリ使用量 54048 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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