QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #74773 | #5022. 【模板】线段树 | MEKHANE | 0 | 1943ms | 7672kb | C++14 | 1.4kb | 2023-02-03 20:38:05 | 2023-02-03 20:38:09 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int N=3e5+5,B=256,M=1e3+5;
int cnt[M],val[M][B],T,n,q,a[N],ks[N],L[M],R[M],m,opt,l,r,tmp1[B],tmp[M][B];
void fwt(int *f,int opt){
for(int i=1;i<B;i*=2)
for(int j=0;j<B;j+=2*i)
rep(k,0,i) (opt?f[j+k]^=f[i+j+k]:f[i+j+k]^=f[j+k]);
}
void pu(int x){rep(i,0,B-1) val[x][i]=(L[x]+i>R[x]?0:a[R[x]-i]); fwt(val[x],0);}
void pd(int x){
rep(i,0,8) if((cnt[x]>>i)&1) per(j,B-1,(1<<i)) a[L[x]+j]^=a[L[x]+j-(1<<i)];
rep(i,0,B-1) tmp1[i]=0;
rep(i,1,cnt[x]) tmp1[cnt[x]-i]=tmp[x][i];
fwt(tmp1,1);
rep(i,0,B-1) a[L[x]+i]^=tmp1[i];
cnt[x]=0;
}
void gx(int l,int r){
if(ks[l]==ks[r]){pd(ks[l]); per(i,r,l+1) a[i]^=a[i-1]; pu(ks[l]);}
else{
pd(ks[l]); int lst=a[R[ks[l]]]; per(i,R[ks[l]],l+1) a[i]^=a[i-1]; pu(ks[l]);
rep(i,ks[l]+1,ks[r]){
tmp[i][++cnt[i]]=lst,lst=val[i][cnt[i]-1];
if(cnt[i]==B-1) pd(i),pu(i);
}
pd(ks[r]); per(i,r,L[ks[r]]+1) a[i]^=a[i-1]; pu(ks[r]);
}
}
signed main(){
scanf("%d%d",&n,&q);
rep(i,1,n) scanf("%d",&a[i]),ks[i]=(i-1)/B+1;
m=ks[n];
rep(i,1,m) L[i]=(i-1)*B+1,R[i]=min(n,i*B),pu(i);
rep(i,1,q){
scanf("%d%d",&opt,&l);
if(opt==1) scanf("%d",&r),gx(l,r);
else pd(ks[l]),pu(ks[l]),printf("%d\n",a[l]);
}
rep(i,1,m) pd(i);
rep(i,1,n) printf("%d\n",a[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5644kb
input:
1 6 6 1 1 5 1 9 4 2 5 1 2 5 2 4 1 3 6 2 6 1 1 6
output:
0 5 5
result:
wrong answer 1st numbers differ - expected: '9', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 1943ms
memory: 7672kb
input:
2 249998 99999 1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 2686th numbers differ - expected: '1048488450', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 1785ms
memory: 6148kb
input:
3 250000 99999 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...
output:
99999 99999 99998 99999 0 0 0 0 99998 0 0 99998 0 99998 0 0 0 99999 99999 0 0 99999 99998 99998 99999 0 0 0 0 99999 0 99998 99998 99998 99998 99998 0 0 0 99998 0 0 99998 0 0 99999 99999 0 0 99999 0 0 99999 99999 0 99999 99999 0 0 99998 99998 99998 99998 0 0 0 0 99999 0 99999 0 99998 0 0 99998 99998 ...
result:
wrong answer 1st numbers differ - expected: '0', found: '99999'
Subtask #4:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
4 249996 99997 309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #18:
score: 0
Runtime Error
input:
5 249997 99997 860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%