結果

問題 No.2223 Merged Med
ユーザー stoq
提出日時 2023-02-16 04:36:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 6,089 ms / 7,000 ms
コード長 2,028 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 293,336 KB
最終ジャッジ日時 2024-07-19 11:55:55
合計ジャッジ時間 92,738 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

# 0: lmax
# 1: rmax
# 2: max
# 3: sum

n = 1
SIZE = 1 << 17
LOG = 17
d = [(0, 0, 0, 0) for _ in range(SIZE * 2)]


def op(s, t):
    return (max(s[0], s[3] + t[0]), max(t[1], s[1] + t[3]),
            max(s[2], t[2], s[1] + t[0]), s[3] + t[3])


def seg_init():
    for i in range(n):
        d[SIZE + i] = (1, 1, 1, 1)
    for i in range(SIZE - 1, 0, -1):
        seg_update(i)


def seg_prod(l, r):
    # assert 0 <= l and l <= r and r <= self.n
    sml = (0, 0, 0, 0)
    smr = (0, 0, 0, 0)
    l += SIZE
    r += SIZE
    while l < r:
        if l & 1:
            sml = op(sml, d[l])
            l += 1
        if r & 1:
            smr = op(d[r - 1], smr)
            r -= 1
        l >>= 1
        r >>= 1
    return op(sml, smr)


def seg_set(p, x):
    # assert 0 <= p and p < n
    p += SIZE
    d[p] = x
    for i in range(1, LOG + 1):
        seg_update(p >> i)


def seg_update(k):
    d[k] = op(d[2 * k], d[2 * k + 1])


n, q = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
l = []
r = []
for _ in range(q):
    li, ri = map(int, input().split())
    l.append(li - 1)
    r.append(ri)
a_idx = [[] for _ in range(n)]
for i in range(n):
    a_idx[a[i]].append(i)
lo = [-1] * q
hi = [n] * q
mi_num = [deque() for _ in range(n)]
for i in range(q):
    mi_num[(lo[i] + hi[i]) >> 1].append(i)

ans_cnt = 0
while ans_cnt < q:
    seg_init()
    for mi in range(n):
        for i in a_idx[mi]:
            seg_set(i, (-1, -1, -1, -1))
        while len(mi_num[mi]) > 0:
            i = mi_num[mi].popleft()
            s = seg_prod(l[i], r[i])
            if s[3] < 0 or s[3] - s[2] + 1 < 0:
                hi[i] = mi
            else:
                lo[i] = mi
            if hi[i] - lo[i] > 1:
                mi_num[lo[i] + ((hi[i] - lo[i]) >> 1)].append(i)
            else:
                ans_cnt += 1
for i in range(q):
    print(hi[i] + 1)
0