Submission #1122450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122450		uranium235	A Huge Tower (CEOI10_tower)	Java	100 / 100	644 ms	86616 KiB

tower

// package ojuz;

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

public class tower {
    public static final long MODULO = (long) 1e9 + 9;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), d = Integer.parseInt(first[1]);
        int[] arr = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(arr);

        // for each block from largest to smallest, calculate how many blocks it can be on top of
        // within the margin d, each permutation of one block being on top of another defines
        // a unique tower, so just multiply all possibilities together
        long result = 1;
        int pointer = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            while (pointer > 0 && arr[pointer - 1] + d >= arr[i]) pointer--;
            result = result * (i - pointer + 1) % MODULO;
        }

        System.out.println(result);
    }
}

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