結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
detteiuu
|
| 提出日時 | 2025-10-05 15:47:36 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 874 ms / 2,000 ms |
| コード長 | 1,223 bytes |
| コンパイル時間 | 265 ms |
| コンパイル使用メモリ | 82,576 KB |
| 実行使用メモリ | 143,032 KB |
| 最終ジャッジ日時 | 2025-10-05 15:48:02 |
| 合計ジャッジ時間 | 18,018 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
class BIT:
def __init__(self, A):
self.size = len(A)
self.bit = [0]*(len(A)+1)
for i in range(len(A)):
self.add(i, A[i])
def sum(self, i):
i += 1
ans = 0
while i > 0:
ans += self.bit[i]
i -= -i&i
return ans
def query(self, l, r):
if l == 0:
return self.sum(r-1)
else:
return self.sum(r-1)-self.sum(l-1)
def add(self, i, x):
i += 1
while i <= self.size:
self.bit[i] += x
i += -i&i
N, Q = map(int, input().split())
A = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(Q)]
INF = 1<<60
L = []
stack = [(INF, -1)]
for i, a in enumerate(A):
while stack[-1][0] < a:
stack.pop()
L.append(stack[-1][1])
stack.append((a, i))
L = sorted(enumerate(L), key=lambda x:x[1], reverse=True)
query = sorted(enumerate(query), key=lambda x:x[1][0], reverse=True)
ans = [-1]*Q
F = BIT([0]*N)
idx = 0
for qidx, (l, r) in query:
l, r = l-1, r-1
while idx < N and l <= L[idx][1]:
F.add(L[idx][0], 1)
idx += 1
ans[qidx] = F.query(l, r+1)
print(*ans, sep="\n")
detteiuu