結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-19 13:12:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 834 bytes |
コンパイル時間 | 353 ms |
コンパイル使用メモリ | 82,652 KB |
実行使用メモリ | 63,964 KB |
最終ジャッジ日時 | 2025-07-19 13:12:38 |
合計ジャッジ時間 | 7,211 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 5 TLE * 1 -- * 14 |
ソースコード
(n,q),a,*e=[[*map(int,s.split())]for s in open(0)] def Add(k): global res for j in range(L,R+1): # print(i,'ADD',j,k,res) res+=a[k]^a[j] def Del(k): global res for j in range(L,R+1): # print(i,'DEL',j,k,res) res-=a[k]^a[j] N=2*10**5+10 #M=Sqrt(Q)個のバケットを作る M=int(q**0.5)+1 bucket=[[] for i in range(M)] #lを基準にして各バケットにqueを振り分け for i,(l,r)in enumerate(e): l-=1;r-=1 bucket[l*M//n]+=(l,r,i), #各バケットをrの降順/昇順にソート for i in range(M): if i&1: bucket[i].sort(key=lambda x:-x[1]) else: bucket[i].sort(key=lambda x:x[1]) ans=[0]*q L=R=res=0 Add(0) for b in bucket: for l,r,i in b: while R<r:R+=1;Add(R) while L>l:L-=1;Add(L) while R>r:Del(R);R-=1 while L<l:Del(L);L+=1 ans[i]=res print(*ans,sep='\n')