結果

問題 No.924 紲星
ユーザー mkawa2mkawa2
提出日時 2024-11-01 12:01:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,307 bytes
コンパイル時間 578 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 282,420 KB
最終ジャッジ日時 2024-11-01 12:01:32
合計ジャッジ時間 8,010 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other WA * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
# sys.setrecursionlimit(200005)
# sys.set_int_max_str_digits(200005)
int1 = lambda x: int(x)-1
pDB = lambda *x: print(*x, end="\n", file=sys.stderr)
p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
# inf = -1-(-1 << 31)
inf = -1-(-1 << 62)
md = 10**9+7
# md = 998244353
#
#
class HeapQ:
def __init__(self, isleft=None):
self._isleft = isleft
if self._isleft == None: self._isleft = lambda a, b: a < b
self._tree = []
self._size = 0
self._pos = {}
self._cnt = {}
self.sum = 0
def __repr__(self):
return "["+",".join(str(a) for a in self._tree for _ in range(self._cnt[a]))+"]"
def _down(self, u):
n = len(self._tree)
while u*2+1 < n:
v = u
if self._isleft(self._tree[u*2+1], self._tree[v]): v = u*2+1
if u*2+2 < n and self._isleft(self._tree[u*2+2], self._tree[v]): v = u*2+2
if u == v: break
self._swap(u, v)
u = v
def _swap(self, u, v):
if u == v: return
a, b = self._tree[u], self._tree[v]
self._tree[u], self._tree[v] = b, a
self._pos[a], self._pos[b] = v, u
def __getitem__(self, index):
return self._tree[index]
def __len__(self):
return self._size
def __contains__(self, item):
return item in self._pos
def push(self, a):
self.sum += a
self._size += 1
if a in self._cnt:
self._cnt[a] += 1
return
self._cnt[a] = 1
u = len(self._tree)
self._tree.append(a)
self._pos[a] = u
v = (u-1)//2
while u and self._isleft(a, self._tree[v]):
self._swap(u, v)
u, v = v, (v-1)//2
def discard(self, item):
if item not in self._pos: return False
self.sum -= item
self._size -= 1
if self._cnt[item] == 1:
u, v = self._pos[item], len(self._tree)-1
self._swap(u, v)
self._tree.pop()
del self._cnt[item]
del self._pos[item]
self._down(u)
else:
self._cnt[item] -= 1
return True
def pop(self):
assert self._size > 0
res = self._tree[0]
self.discard(res)
return res
def mos_algorithm(lr, max_r):
q = len(lr)
h = round(max_r**0.5) if max_r < q else round(max_r/q**0.5)
gn = (max_r-1)//h+1
qilr = [[] for _ in range(gn)]
for qi, (l, r) in enumerate(lr): qilr[l//h].append((qi, l, r))
ans = [-1]*q
L = R = 0
for g in range(gn):
qilr[g].sort(key=lambda x: -x[2] if g & 1 else x[2])
for qi, l, r in qilr[g]:
while L > l: L, _ = L-1, insL(L, R)
while R < r: R, _ = R+1, insR(L, R)
while R > r: R, _ = R-1, remR(L, R)
while L < l: L, _ = L+1, remL(L, R)
trim()
med = hr[0]
ans[qi] = med*len(hl)-hl.sum+hr.sum-med*len(hr)
return ans
# insert aa[i]
def insL(L, R):
a = aa[L-1]
hl.push(a)
def insR(L, R):
a = aa[R]
hl.push(a)
# remove aa[i]
def remL(L, R):
a = aa[L]
if a in hl:
hl.discard(a)
else:
hr.discard(a)
def remR(L, R):
a = aa[R-1]
if a in hl:
hl.discard(a)
else:
hr.discard(a)
def trim():
while len(hl)<len(hr)-1:
x=hr.pop()
hl.push(x)
while len(hl)>len(hr):
x=hl.pop()
hr.push(x)
while hl and hl[0]>hr[0]:
x=hl.pop()
y=hr.pop()
hl.push(y)
hr.push(x)
n, q = LI()
aa = LI()
lr = []
for _ in range(q):
l, r = LI()
lr.append((l-1, r))
hl = HeapQ(lambda a, b: a > b)
hr = HeapQ()
ans = mos_algorithm(lr, n)
print(*ans, sep="\n")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0