N, D = map(int, input().split())
blocks = sorted(list(map(int, input().split())))
def binary_search_i(l, r, size, list):
ans = r + 1
while r >= l:
m = (l + r) // 2
# m = l + floor(log10(r - l + 1))
# m = l + (r - l) // 1000000
if size <= list[m] + D:
r = m - 1
ans = m
else:
l = m + 1
return ans
def binary_search_j(l, r, size, list):
ans = r + 1
while r >= l:
m = (l + r) // 2
if list[m] > size + D:
r = m - 1
ans = m
else:
l = m + 1
return ans
ans = 1
i = 0
j = 1
while j < N:
prev_j = j
# while i < j and blocks[j] > blocks[i] + D:
# i += 1
i = binary_search_i(i, j - 1, blocks[j], blocks)
if i < j:
j = binary_search_j(prev_j, N - 1, blocks[i], blocks)
for k in range(prev_j, j):
if k - i == 1:
ans = ans << 1
else:
ans *= k - i + 1
else:
j += 1
print(ans % 1000000009)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
2840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
2984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
3004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
4052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
8420 KB |
Output is correct |
2 |
Correct |
535 ms |
8372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
30584 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
72924 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |