結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー nouka28nouka28
提出日時 2024-10-04 00:05:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,707 ms / 5,000 ms
コード長 1,670 bytes
コンパイル時間 123 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 296,796 KB
最終ジャッジ日時 2024-10-04 00:07:10
合計ジャッジ時間 62,407 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 489 ms
247,920 KB
testcase_01 AC 451 ms
248,072 KB
testcase_02 AC 476 ms
248,156 KB
testcase_03 AC 2,516 ms
278,740 KB
testcase_04 AC 3,185 ms
293,172 KB
testcase_05 AC 3,707 ms
293,196 KB
testcase_06 AC 3,574 ms
293,948 KB
testcase_07 AC 2,774 ms
289,140 KB
testcase_08 AC 2,601 ms
292,176 KB
testcase_09 AC 3,025 ms
296,476 KB
testcase_10 AC 3,044 ms
296,796 KB
testcase_11 AC 2,147 ms
292,256 KB
testcase_12 AC 2,818 ms
277,388 KB
testcase_13 AC 2,906 ms
274,752 KB
testcase_14 AC 3,197 ms
292,436 KB
testcase_15 AC 2,654 ms
278,752 KB
testcase_16 AC 2,334 ms
271,724 KB
testcase_17 AC 2,908 ms
290,032 KB
testcase_18 AC 2,949 ms
289,164 KB
testcase_19 AC 2,538 ms
272,804 KB
testcase_20 AC 2,614 ms
277,752 KB
testcase_21 AC 2,163 ms
275,272 KB
testcase_22 AC 2,470 ms
278,016 KB
testcase_23 AC 2,760 ms
277,176 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=min(sum(v),R-L-sum([not i for i in v]))

    print(res)

    res_prev=res
0