結果

問題 No.924 紲星
ユーザー mkawa2mkawa2
提出日時 2024-11-01 01:07:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,562 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 80,872 KB
最終ジャッジ日時 2024-11-01 01:07:43
合計ジャッジ時間 8,264 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 3 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 = {}
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._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._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)
# print(qi, l, r, sl, sr, hl, hr)
med = hr[0]
ans[qi] = med*len(hl)-sl+sr-med*len(hr)
return ans
# insert aa[i]
def insL(L, R):
a = aa[L-1]
push(a)
def insR(L, R):
a = aa[R]
push(a)
# remove aa[i]
def remL(L, R):
a = aa[L]
remove(a)
def remR(L, R):
a = aa[R-1]
remove(a)
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()
sl = sr = 0
def push(a):
global sl, sr
if len(hl) < len(hr):
hl.push(a)
sl += a
else:
hr.push(a)
sr += a
if hl and hl[0] > hr[0]:
x = hl.pop()
y = hr.pop()
hl.push(y)
hr.push(x)
sl += y-x
sr += x-y
def remove(a):
global sl, sr
if a >= hr[0]:
hr.discard(a)
sr -= a
if len(hl) > len(hr):
x = hl.pop()
hr.push(x)
sl -= x
sr += x
else:
hl.discard(a)
sl -= a
if len(hl) == len(hr)-2:
y = hr.pop()
hl.push(y)
sl += y
sr -= y
ans = mos_algorithm(lr, n)
print(*ans, sep="\n")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0