QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408079#6533. Traveling in Cellsx17875487211WA 176ms5892kbC++144.5kb2024-05-09 17:50:582024-05-09 17:50:59

Judging History

你现在查看的是最新测评结果

  • [2024-05-09 17:50:59]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:5892kb
  • [2024-05-09 17:50:58]
  • 提交

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'