結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
60,540 KB
testcase_01 AC 35 ms
53,988 KB
testcase_02 AC 36 ms
54,008 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

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")
0