結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 |
ソースコード
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