# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
927537 | ay136416 | A Huge Tower (CEOI10_tower) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
public class Towers {
final static long MOD = 1_000_000_009;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader();
String[] tokens = br.readLine().split(" ");
final int N = Integer.parseInt(tokens[0]);
final int D = Integer.parseInt(tokens[1]);
int[] blocks = new int[N];
tokens = br.readLine().split(" ");
for (int i = 0; i<N; i++) {
blocks[i]=Integer.parseInt(tokens[i]);
}
Arrays.sort(blocks);
long ans = 1;
int right = 0;
for (int left = 0; left<N; left++) {
while (right<N-1 && blocks[right+1]-blocks[left]<=D)
right++;
ans *= (right-left+1);
ans %= MOD;
}
System.out.println(ans);
}
}