結果

問題 No.2223 Merged Med
ユーザー stoqstoq
提出日時 2023-02-16 04:36:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 6,457 ms / 7,000 ms
コード長 2,028 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 87,016 KB
実行使用メモリ 298,464 KB
最終ジャッジ日時 2023-09-26 17:59:02
合計ジャッジ時間 100,469 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 140 ms
90,500 KB
testcase_01 AC 110 ms
79,148 KB
testcase_02 AC 146 ms
90,508 KB
testcase_03 AC 141 ms
90,660 KB
testcase_04 AC 152 ms
90,524 KB
testcase_05 AC 181 ms
101,120 KB
testcase_06 AC 150 ms
90,660 KB
testcase_07 AC 196 ms
101,524 KB
testcase_08 AC 216 ms
112,316 KB
testcase_09 AC 203 ms
112,016 KB
testcase_10 AC 191 ms
101,212 KB
testcase_11 AC 147 ms
90,512 KB
testcase_12 AC 150 ms
90,880 KB
testcase_13 AC 2,962 ms
280,004 KB
testcase_14 AC 1,836 ms
205,388 KB
testcase_15 AC 4,170 ms
294,724 KB
testcase_16 AC 5,295 ms
285,968 KB
testcase_17 AC 2,773 ms
271,316 KB
testcase_18 AC 1,782 ms
212,376 KB
testcase_19 AC 2,597 ms
268,324 KB
testcase_20 AC 6,290 ms
298,364 KB
testcase_21 AC 6,202 ms
295,420 KB
testcase_22 AC 6,269 ms
296,760 KB
testcase_23 AC 6,202 ms
295,840 KB
testcase_24 AC 6,097 ms
298,464 KB
testcase_25 AC 6,457 ms
294,504 KB
testcase_26 AC 6,364 ms
295,460 KB
testcase_27 AC 6,006 ms
296,328 KB
testcase_28 AC 5,992 ms
297,380 KB
testcase_29 AC 6,332 ms
295,968 KB
testcase_30 AC 1,992 ms
280,128 KB
testcase_31 AC 735 ms
155,732 KB
testcase_32 AC 220 ms
95,764 KB
testcase_33 AC 5,133 ms
278,772 KB
testcase_34 AC 2,749 ms
269,268 KB
testcase_35 AC 1,094 ms
158,668 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