제출 #809188

#제출 시각아이디문제언어결과실행 시간메모리
809188jackliy369A Huge Tower (CEOI10_tower)Cpython 3
90 / 100
1078 ms72924 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...