Submission #492312

#	Time	Username	Problem	Language	Result	Execution time	Memory
492312		mosiashvililuka	Crossing (JOI21_crossing)	C++14	26 / 100	213 ms	11792 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,seg[800009],seg2[800009],pr[5][200009],l,r,z,zz,za;
string S[9],s;
char ch;
void pushdown(int q, int w, int rr){
	if(seg2[rr]==0) return;
	if(q!=w){
		seg2[rr*2]=seg2[rr];
		seg2[rr*2+1]=seg2[rr];
	}
	seg[rr]=pr[seg2[rr]][w]-pr[seg2[rr]][q-1];
	seg2[rr]=0;
}
void upd(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		seg2[rr]=z;
		pushdown(q,w,rr);
		return;
	}
	upd(q,(q+w)/2,rr*2);
	upd((q+w)/2+1,w,rr*2+1);
	seg[rr]=seg[rr*2]+seg[rr*2+1];
}
void read(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		z+=seg[rr];
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	cin>>S[1]>>S[2]>>S[3];
	for(i=1; i<=3; i++) S[i]="0"+S[i];
	cin>>tes;
	cin>>s;s="0"+s;
	za=1;
	while(za<a) za*=2;
	for(i=1; i<=a; i++){
		if(S[1][i]!=s[i]) break;
	}
	if(i==a+1){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	for(i=1; i<=a; i++){
		for(j=1; j<=3; j++) pr[j][i]=pr[j][i-1];
		if(S[1][i]=='J') e=1;
		if(S[1][i]=='O') e=2;
		if(S[1][i]=='I') e=3;
		pr[e][i]++;
	}
	for(i=1; i<=a; i++){
		if(S[1][i]==s[i]){
			seg[za+i-1]=1;
		}
	}
	for(i=za-1; i>=1; i--){
		seg[i]=seg[i*2]+seg[i*2+1];
	}
	/*l=1;r=a;z=0;
	read(1,za,1);
	cout<<z<<"\n";*/
	for(t=1; t<=tes; t++){
		cin>>c>>d>>ch;
		if(ch=='J') z=1;
		if(ch=='O') z=2;
		if(ch=='I') z=3;
		l=c;r=d;
		upd(1,za,1);
		l=1;r=a;z=0;
		read(1,za,1);
		if(z==a){
			cout<<"Yes\n";
		}else{
			cout<<"No\n";
		}
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51