結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー nouka28nouka28
提出日時 2024-09-27 04:18:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,321 ms / 5,000 ms
コード長 1,834 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 295,904 KB
最終ジャッジ日時 2024-09-27 04:49:19
合計ジャッジ時間 76,810 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 558 ms
248,304 KB
testcase_01 AC 545 ms
247,812 KB
testcase_02 AC 564 ms
248,180 KB
testcase_03 AC 3,055 ms
278,096 KB
testcase_04 AC 4,110 ms
292,508 KB
testcase_05 AC 4,321 ms
292,996 KB
testcase_06 AC 4,310 ms
293,512 KB
testcase_07 AC 3,291 ms
289,844 KB
testcase_08 AC 3,116 ms
292,232 KB
testcase_09 AC 3,695 ms
295,904 KB
testcase_10 AC 3,836 ms
295,368 KB
testcase_11 AC 2,616 ms
291,908 KB
testcase_12 AC 3,490 ms
276,996 KB
testcase_13 AC 3,448 ms
274,816 KB
testcase_14 AC 3,947 ms
292,740 KB
testcase_15 AC 3,127 ms
278,632 KB
testcase_16 AC 2,839 ms
271,524 KB
testcase_17 AC 3,800 ms
289,500 KB
testcase_18 AC 3,807 ms
288,732 KB
testcase_19 AC 3,191 ms
272,864 KB
testcase_20 AC 3,265 ms
277,032 KB
testcase_21 AC 2,570 ms
275,476 KB
testcase_22 AC 3,039 ms
278,304 KB
testcase_23 AC 3,357 ms
276,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n=int(input())
a=list(map(int,input().split()))

P=[i for i in range(n)]

T=400000
dp=[[]for i in range(3*T)]
dp2=[[]for i in range(3*T)]

def build(l:int,r:int,k:int,idx:list)->None:
    global dp,dp2
    for C in range(1,4):
        R=0
        now=0

        cnt=[0]*(r-l)

        for i in range(len(idx)):
            assert i<=R

            while R<len(idx) and now<r-l:
                cnt[a[idx[R]]-l]+=1
                if cnt[a[idx[R]]-l]==C:
                    now+=1
                R+=1
            
            if now==r-l:
                dp[(C-1)*T+k].append(idx[i])
                dp2[(C-1)*T+k].append(idx[R-1])
            
            if cnt[a[idx[i]]-l]==C:
                now-=1
            
            cnt[a[idx[i]]-l]-=1
        dp[(C-1)*T+k].append(10**9)
        dp2[(C-1)*T+k].append(10**9)

    if r-l==1:return

    idxL=[]
    idxR=[]
    mid=(l+r)//2

    for e in idx:
        if a[e]<mid:idxL.append(e)
        else:idxR.append(e)
    
    build(l,mid,2*k+1,idxL)
    build(mid,r,2*k+2,idxR)

def search(l:int,r:int,k:int,C:int,L:int,R:int)->int:
    p=bisect.bisect_left(dp[(C-1)*T+k],L)
    p=dp2[(C-1)*T+k][p]

    if p<R:return r
    if r-l==1:return l

    mid=(l+r)//2
    res=search(l,mid,2*k+1,C,L,R)
    if res<mid:return res
    else:return search(mid,r,2*k+2,C,L,R)

build(0,100001,0,P)

q=int(input())

res_prev=0

while q:
    q-=1

    x,y=map(int,input().split())

    L=(x^res_prev)-1
    R=y^res_prev

    # print("L R : ",L,R)

    assert 0<=L and R-L>=2 and R<=n

    v=[search(0,100001,0,C,L,R)for C in range(1,4)]

    res=0

    if v[2]:
        res=v[0]+v[1]+v[2]
    elif v[1]:
        res=v[0]+v[1]+min(0,R-L-v[0]-v[1]-1)
    elif v[0]:
        res=v[0]+min(0,R-L-v[0]-2)
    else:
        res=0

    # print("res : ",res)

    print(res)

    res_prev=res
0