結果
問題 | No.924 紲星 |
ユーザー |
![]() |
提出日時 | 2024-11-02 00:07:57 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,422 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 80,176 KB |
最終ジャッジ日時 | 2024-11-02 00:08:07 |
合計ジャッジ時間 | 8,014 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 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 = {}self.sum = 0def __repr__(self):return "["+",".join(str(a) for a in self._tree for _ in range(self._cnt[a]))+"]"def _up(self,u):if u>=len(self._tree):returnv = (u-1)//2while u and self._isleft(self._tree[u], self._tree[v]):self._swap(u, v)u, v = v, (v-1)//2def _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.sum += aself._size += 1if a in self._cnt:self._cnt[a] += 1returnself._cnt[a] = 1u = len(self._tree)self._tree.append(a)self._pos[a] = uself._up(u)def discard(self, item):if item not in self._pos: return Falseself.sum -= itemself._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._up(u)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)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")