結果
問題 | No.2935 Division Into 3 (Mex Edition) |
ユーザー |
|
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
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