結果

問題 No.2223 Merged Med
ユーザー stoqstoq
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
89,344 KB
testcase_01 AC 61 ms
74,112 KB
testcase_02 AC 115 ms
100,096 KB
testcase_03 AC 92 ms
89,364 KB
testcase_04 AC 116 ms
99,840 KB
testcase_05 AC 128 ms
100,224 KB
testcase_06 AC 115 ms
100,012 KB
testcase_07 AC 146 ms
100,480 KB
testcase_08 AC 165 ms
110,592 KB
testcase_09 AC 156 ms
110,720 KB
testcase_10 AC 139 ms
100,388 KB
testcase_11 AC 114 ms
100,096 KB
testcase_12 AC 117 ms
99,792 KB
testcase_13 AC 2,630 ms
271,956 KB
testcase_14 AC 1,673 ms
199,184 KB
testcase_15 AC 3,690 ms
289,728 KB
testcase_16 AC 4,945 ms
291,948 KB
testcase_17 AC 2,624 ms
281,656 KB
testcase_18 AC 1,648 ms
208,000 KB
testcase_19 AC 2,372 ms
259,324 KB
testcase_20 AC 5,810 ms
292,392 KB
testcase_21 AC 5,811 ms
291,856 KB
testcase_22 AC 5,857 ms
293,336 KB
testcase_23 AC 5,717 ms
291,992 KB
testcase_24 AC 5,776 ms
292,428 KB
testcase_25 AC 5,789 ms
292,424 KB
testcase_26 AC 5,823 ms
291,548 KB
testcase_27 AC 6,089 ms
293,116 KB
testcase_28 AC 5,605 ms
292,280 KB
testcase_29 AC 5,791 ms
290,924 KB
testcase_30 AC 1,861 ms
280,016 KB
testcase_31 AC 704 ms
155,064 KB
testcase_32 AC 171 ms
94,720 KB
testcase_33 AC 4,734 ms
288,444 KB
testcase_34 AC 2,560 ms
279,764 KB
testcase_35 AC 996 ms
156,452 KB
権限があれば一括ダウンロードができます

ソースコード

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