結果
問題 | No.924 紲星 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sys# sys.setrecursionlimit(200005)# sys.set_int_max_str_digits(200005)int1 = lambda x: int(x)-1pDB = 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 = isleftif self._isleft == None: self._isleft = lambda a, b: a < bself._tree = []self._size = 0self._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 = uif self._isleft(self._tree[u*2+1], self._tree[v]): v = u*2+1if u*2+2 < n and self._isleft(self._tree[u*2+2], self._tree[v]): v = u*2+2if u == v: breakself._swap(u, v)u = vdef _swap(self, u, v):if u == v: returna, b = self._tree[u], self._tree[v]self._tree[u], self._tree[v] = b, aself._pos[a], self._pos[b] = v, udef __getitem__(self, index):return self._tree[index]def __len__(self):return self._sizedef __contains__(self, item):return item in self._posdef push(self, a):self._size += 1if a in self._cnt:self._cnt[a] += 1returnself._cnt[a] = 1u = len(self._tree)self._tree.append(a)self._pos[a] = uv = (u-1)//2while u and self._isleft(a, self._tree[v]):self._swap(u, v)u, v = v, (v-1)//2def discard(self, item):if item not in self._pos: return Falseself._size -= 1if self._cnt[item] == 1:u, v = self._pos[item], len(self._tree)-1self._swap(u, v)self._tree.pop()del self._cnt[item]del self._pos[item]self._down(u)else:self._cnt[item] -= 1return Truedef pop(self):assert self._size > 0res = self._tree[0]self.discard(res)return resdef 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+1qilr = [[] for _ in range(gn)]for qi, (l, r) in enumerate(lr): qilr[l//h].append((qi, l, r))ans = [-1]*qL = R = 0for 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 = 0def push(a):global sl, srif len(hl) < len(hr):hl.push(a)sl += aelse:hr.push(a)sr += aif hl and hl[0] > hr[0]:x = hl.pop()y = hr.pop()hl.push(y)hr.push(x)sl += y-xsr += x-ydef remove(a):global sl, srif a >= hr[0]:hr.discard(a)sr -= aif len(hl) > len(hr):x = hl.pop()hr.push(x)sl -= xsr += xelse:hl.discard(a)sl -= aif len(hl) == len(hr)-2:y = hr.pop()hl.push(y)sl += ysr -= yans = mos_algorithm(lr, n)print(*ans, sep="\n")