제출 #1166874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166874		mertbbm	Crossing (JOI21_crossing)	C++20	100 / 100	2679 ms	341764 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string f(string a, string b){
	string temp="";
	for(int x=0;x<n;x++){
		if(a[x]==b[x]) temp+=a[x];
		else{
			if(a[x]!='J'&&b[x]!='J') temp.push_back('J');
			if(a[x]!='O'&&b[x]!='O') temp.push_back('O');
			if(a[x]!='I'&&b[x]!='I') temp.push_back('I');
		}
	}
	return temp;
}

int f2(char a){
	if(a=='J') return 1;
	else if(a=='O') return 2;
	else return 3;
}

string target;

struct node{
	int s,e,m;
	node *l,*r;
	bool v;
	int lazySet;
	int lset;
	int mini;
	int maxi;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazySet(0),mini(0),maxi(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			mini=min(l->mini,r->mini);
			maxi=max(l->maxi,r->maxi);
			v=l->v&r->v;
		}
		else{
			v=true;
			mini=f2(target[s]);
			maxi=f2(target[s]);
		}
	}
	
	void self_set(int x){
		//set ur own
		if(mini==maxi&&mini==x){
			v=true;
		}
		else v=false;
		lazySet=x;
		lset=true;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lset){
			l->self_set(lazySet);
			r->self_set(lazySet);
			lazySet=0;
			lset=0;
		} 
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_set(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v=l->v&r->v;
	}
}*root[9];

void ans(){
	bool amos=false;
	for(int x=0;x<9;x++){
		if(root[x]->v) amos=true;
	}
	if(amos) cout << "Yes\n";
	else cout << "No\n";
}

void solve(){
	cin >> n;
	string arr[9];
	cin >> arr[0] >> arr[1] >> arr[2];
	
	//abc
	arr[3]=f(arr[0],arr[1]);
	arr[4]=f(arr[3],arr[2]);
	//acb
	arr[5]=f(arr[0],arr[2]);
	arr[6]=f(arr[5],arr[1]);
	//bca
	arr[7]=f(arr[1],arr[2]);
	arr[8]=f(arr[7],arr[0]);
	
	for(int x=0;x<9;x++){
		target=arr[x];
		root[x]=new node(0,n-1);
	}
	
	int q;
	cin >> q;
	string s;
	cin >> s;
	for(int x=0;x<n;x++){
		for(int y=0;y<9;y++){
			root[y]->rangeUpd(x,x,f2(s[x]));
		}
	}
	
	ans();
	
	int l,r,val;
	char temp;
	for(int x=0;x<q;x++){
		cin >> l >> r >> temp;
		val=f2(temp);
		l--; r--;
		
		for(int y=0;y<9;y++){
			root[y]->rangeUpd(l,r,val);
		}
		
		ans();
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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