QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#408079 | #6533. Traveling in Cells | x17875487211 | WA | 176ms | 5892kb | C++14 | 4.5kb | 2024-05-09 17:50:58 | 2024-05-09 17:50:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
int T,n,nn,q,C[maxn],V[maxn],JumpL[maxn<<2],JumpR[maxn<<2],Sum[maxn<<2],Pre[maxn],Suf[maxn],lazL[maxn<<2],lazR[maxn<<2];
void bui_JumpL(int t,int l,int r){
JumpL[t]=lazL[t]=0;
if(l==r){
Pre[l]=((C[l]==C[l-1])?Pre[l-1]:l);
JumpL[t]=Pre[l];
return;
}
int mid=(l+r)>>1;
bui_JumpL(t<<1,l,mid);
bui_JumpL(t<<1|1,mid+1,r);
}
void bui_JumpR(int t,int l,int r){
JumpR[t]=lazR[t]=0;
if(l==r){
Suf[l]=((C[l]==C[l+1])?Suf[l+1]:l);
JumpR[t]=Suf[l];
return;
}
int mid=(l+r)>>1;
bui_JumpR(t<<1|1,mid+1,r);
bui_JumpR(t<<1,l,mid);
}
void pdL(int t){
if(!lazL[t]) return;
JumpL[t<<1]=lazL[t];
lazL[t<<1]=lazL[t];
JumpL[t<<1|1]=lazL[t];
lazL[t<<1|1]=lazL[t];
lazL[t]=0;
}
void pdR(int t){
if(!lazR[t]) return;
JumpR[t<<1]=lazR[t];
lazR[t<<1]=lazR[t];
JumpR[t<<1|1]=lazR[t];
lazR[t<<1|1]=lazR[t];
lazR[t]=0;
}
int que_JumpL(int t,int l,int r,int pos){
if(l==r) return JumpL[t];
int mid=(l+r)>>1;
pdL(t);
if(pos<=mid) return que_JumpL(t<<1,l,mid,pos);
else return que_JumpL(t<<1|1,mid+1,r,pos);
}
int que_JumpR(int t,int l,int r,int pos){
if(l==r) return JumpR[t];
int mid=(l+r)>>1;
pdR(t);
if(pos<=mid) return que_JumpR(t<<1,l,mid,pos);
else return que_JumpR(t<<1|1,mid+1,r,pos);
}
void upd_JumpL(int t,int l,int r,int x,int y,int val){
if(x<=l&&r<=y){
lazL[t]=val;
JumpL[t]=val;
return;
}
pdL(t);
int mid=(l+r)>>1;
if(x<=mid) upd_JumpL(t<<1,l,mid,x,y,val);
if(y>mid) upd_JumpL(t<<1|1,mid+1,r,x,y,val);
}
void upd_JumpR(int t,int l,int r,int x,int y,int val){
if(x<=l&&r<=y){
lazR[t]=val;
JumpR[t]=val;
return;
}
pdR(t);
int mid=(l+r)>>1;
if(x<=mid) upd_JumpR(t<<1,l,mid,x,y,val);
if(y>mid) upd_JumpR(t<<1|1,mid+1,r,x,y,val);
}
void bui_Sum(int t,int l,int r){
Sum[t]=0;
if(l==r){
Sum[t]=V[l];
return;
}
int mid=(l+r)>>1;
bui_Sum(t<<1,l,mid);
bui_Sum(t<<1|1,mid+1,r);
Sum[t]=Sum[t<<1]+Sum[t<<1|1];
}
void upd_Sum(int t,int l,int r,int pos,int val){
if(l==r){
Sum[t]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) upd_Sum(t<<1,l,mid,pos,val);
else upd_Sum(t<<1|1,mid+1,r,pos,val);
Sum[t]=Sum[t<<1]+Sum[t<<1|1];
}
int que_Sum(int t,int l,int r,int x,int y){
if(x<=l&&r<=y) return Sum[t];
int mid=(l+r)>>1,ret=0;
if(x<=mid) ret+=que_Sum(t<<1,l,mid,x,y);
if(y>mid) ret+=que_Sum(t<<1|1,mid+1,r,x,y);
return ret;
}
void CombL(int l,int r){
upd_JumpL(1,1,nn,l,r,l);
}
void CombR(int l,int r){
upd_JumpR(1,1,nn,l,r,r);
}
void wk(int pos,int col){
if(col==C[pos]) return;
C[pos]=col;
int L=que_JumpL(1,1,nn,pos-1),R=que_JumpR(1,1,nn,pos+1);
if(C[pos-1]==C[pos]&&C[pos]==C[pos+1]){
CombL(L,R),
CombR(L,R);
}
else if(C[pos-1]!=C[pos]&&C[pos]!=C[pos+1]){
if(pos-1>=1)
CombL(L,pos-1),
CombR(L,pos-1);
if(pos+1<=n)
CombL(pos+1,R),
CombR(pos+1,R);
CombL(pos,pos);
}
else if(C[pos-1]!=C[pos]&&C[pos]==C[pos+1]){
if(pos-1>=1)
CombL(L,pos-1),
CombR(L,pos-1);
if(pos+1<=n)
CombL(pos,R),
CombR(pos,R);
}
else if(C[pos-1]==C[pos]&&C[pos]!=C[pos+1]){
if(pos-1>=1)
CombL(L,pos),
CombR(L,pos);
if(pos+1<=n)
CombL(pos+1,R),
CombR(pos+1,R);
}
}
set<int>st;
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&q);
C[0]=C[n+1]=V[0]=V[n+1]=0;
for(int i=1;i<=n;i++) scanf("%lld",&C[i]);
for(int i=1;i<=n;i++) scanf("%lld",&V[i]);
nn=0;while((1<<nn)<n) nn++;nn=1<<nn;
bui_JumpL(1,1,nn);
bui_JumpR(1,1,nn);
bui_Sum(1,1,nn);
while(q--){
int op;scanf("%lld",&op);
if(op==1){
int p,x;scanf("%lld%lld",&p,&x);
wk(p,x);
}
else if(op==2){
int p,x;scanf("%lld%lld",&p,&x);
upd_Sum(1,1,nn,p,x);
}
else{
int x,k;scanf("%lld%lld",&x,&k);
st.clear();
for(int i=1;i<=k;i++){
int col;scanf("%lld",&col);
st.insert(col);
}
int l=x,r=x;
while(l-1>=1&&st.find(C[l-1])!=st.end()){
l=que_JumpL(1,1,nn,l-1);
}
while(r+1<=n&&st.find(C[r+1])!=st.end()){
r=que_JumpR(1,1,nn,r+1);
}
printf("%lld\n",que_Sum(1,1,nn,l,r));
}
}
}
return 0;
}
/*
2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4
1
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5772kb
input:
2 5 10 1 2 3 1 2 1 10 100 1000 10000 3 3 1 3 3 3 2 2 3 2 5 20000 2 3 200 3 3 2 1 3 3 3 3 1 2 3 1 3 4 2 1 100000 1 2 2 3 1 2 1 2 4 1 1 2 3 4 1000000 1000000 1000000 1000000 3 4 4 1 2 3 4
output:
100 110 1200 21211 100010 4000000
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 176ms
memory: 5892kb
input:
20000 15 15 1 1 3 3 2 3 3 3 3 3 2 3 2 3 3 634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831 3 6 4 1 3 5 10 3 5 7 1 2 3 4 5 9 10 3 4 3 3 8 9 2 13 608033129 3 15 2 3 5 1 9 3 3 8 4 1 3 7 10 2 6 727472865 3...
output:
2689089686 8377825475 1706073651 1439027604 2689089686 792730352 8904867081 8904867081 8270273108 831633445 692051585 2782432626 697783016 883944422 184057757 287523250 184057757 696388752 184057757 1675459344 2667693025 2614711258 4006992373 1767091974 5348541057 5348541057 390631780 2290216252 942...
result:
wrong answer 452nd numbers differ - expected: '2072632881', found: '4380061817'