제출 #532733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532733		Cubik65536	A Huge Tower (CEOI10_tower)	Java	30 / 100	665 ms	46112 KiB

tower

import java.io.*;
import java.util.*;

public class tower {
    private static final int MOD = (int) 1e9 + 9;

    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();

        int n = io.nextInt();
        int d = io.nextInt();

        int[] blocks = new int[n];
        for (int i = 0; i < n; i++) {
            blocks[i] = io.nextInt();
        }

        Arrays.sort(blocks);

        int result = 1;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n - 1 && blocks[j + 1] - blocks[i] <= d) {
                j++;
            }
            int dist = j - i + 1;
            result = (result * dist) % MOD;
        }

        io.println(result);

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;

    // standard input
    public Kattio() {
        this(System.in, System.out);
    }

    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }

    // USACO-style file input
    public Kattio(String problemName) throws IOException {
        super(new FileWriter(problemName + ".out"));
        r = new BufferedReader(new FileReader(problemName + ".in"));
    }

    // read next line
    public String readLine() {
        try {
            return r.readLine();
        } catch (IOException e) {
        }
        return null;
    }

    // returns null if no more input
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {
        }
        return null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5