Submission #537630

#	Time	Username	Problem	Language	Result	Execution time	Memory
537630		S2speed	Crossing (JOI21_crossing)	C++17	49 / 100	7056 ms	28728 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) x.begin() , x.end()
#define sze(x) (int)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 2e5 + 16 , maxsq = 450 , inf = 2e16;

set<vector<int>> s;

vector<int> operator+ (vector<int> a , vector<int> b){
	vector<int> res(27);
	for(int i = 0 ; i < 27 ; i++){
		if(a[i] == b[i]){
			res[i] = a[i];
		} else {
			res[i] = 3 - a[i] - b[i];
		}
	}
	return res;
}

vector<int> v[27] , a[27];
int cnt[27][maxsq][3] , Cnt[27][3] , sq[27] , f[maxn] , laz[27][maxsq] , lb[27][maxn] , vs[27];

void relax(int k , int j){
	if(laz[k][j] == -1) return;
	int l = j * sq[k] , r = min(l + sq[k] , vs[k]);
	for(int i = l ; i < r ; i++){
		a[k][i] = laz[k][j];
	}
	laz[k][j] = -1;
	return;
}

void sett(int k , int l , int r , int c){
	int jl = l / sq[k] , jr = r / sq[k];
	if(jl == jr){
		int j = jl;
		relax(k , jl);
		for(int i = l ; i < r ; i++){
			cnt[k][j][a[k][i]]--;
			Cnt[k][a[k][i]]--;
			a[k][i] = c;
			cnt[k][j][a[k][i]]++;
			Cnt[k][a[k][i]]++;
		}
		return;
	}
	relax(k , jl);
	while(l % sq[k]){
		cnt[k][jl][a[k][l]]--;
		Cnt[k][a[k][l]]--;
		a[k][l] = c;
		cnt[k][jl][a[k][l]]++;
		Cnt[k][a[k][l]]++;
		l++;
	}
	relax(k , jr);
	while(r % sq[k]){
		r--;
		cnt[k][jr][a[k][r]]--;
		Cnt[k][a[k][r]]--;
		a[k][r] = c;
		cnt[k][jr][a[k][r]]++;
		Cnt[k][a[k][r]]++;
	}
	for(int j = l / sq[k] , i = l ; j < jr ; j++ , i += sq[k]){
		Cnt[k][0] -= cnt[k][j][0];
		Cnt[k][1] -= cnt[k][j][1];
		Cnt[k][2] -= cnt[k][j][2];
		cnt[k][j][0] = cnt[k][j][1] = cnt[k][j][2] = 0;
		cnt[k][j][c] = min(i + sq[k] , vs[k]) - i;
		Cnt[k][c] += cnt[k][j][c];
		laz[k][j] = c;
	}
	return;
}

bool check(){
	auto it = s.begin() , et = s.end();
	while(it != et){
		vector<int> h = *it; ++it;
		bool res = true;
		for(int k = 0 ; k < 27 && res ; k++){
			if(Cnt[k][0] > 0 && h[k] != 0){
				res = false;
			}
			if(Cnt[k][1] > 0 && h[k] != 1){
				res = false;
			}
			if(Cnt[k][2] > 0 && h[k] != 2){
				res = false;
			}
		}
		if(res) return true;
	}
	return false;
}

/*
5
JJJJJ
JJJJJ
JJJJJ
2
JIIII
2 4 J
3 5 J
*/

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(f , 0 , sizeof(f));
	memset(Cnt , 0 , sizeof(Cnt));
	memset(cnt , 0 , sizeof(cnt));
	memset(laz , -1 , sizeof(laz));
	vector<int> g(27);
	int o = 27;
	for(int t = 0 ; t < 3 ; t++){
		for(int i = 0 ; i < 27 ; i++){
			int h = i % o;
			g[i] = h / (o / 3);
//			cout<<a[i]<<' ';
		}
//		cout<<'\n';
		o /= 3;
		s.insert(g);
	}
	bool hm = true;
	while(hm){
		hm = false;
		auto et = s.end();
		for(auto it = s.begin() ; it != et && !hm ; ++it){
			for(auto jt = it ; jt != et && !hm ; ++jt){
				vector<int> res = (*it) + (*jt);
				if(!s.count(res)){
					s.insert(res);
					hm = true;
				}
			}
		}
	}
//	cout<<"---------------------------\n";
//	auto it = s.begin() , et = s.end();
//	while(it != et){
//		vector<int> res = *it;
//		for(int i = 0 ; i < 27 ; i++){
//			cout<<res[i]<<' ';
//		}
//		cout<<'\n';
//		++it;
//	}
	int n;
	cin>>n;
	o = 9;
	for(int t = 0 ; t < 3 ; t++){
		for(int i = 0 ; i < n ; i++){
			int h;
			char c;
			cin>>c;
			if(c == 'J'){
				h = 0;
			} else if(c == 'O'){
				h = 1;
			} else {
				h = 2;
			}
			f[i] += h * o;
		}
		o /= 3;
	}
	int q;
	cin>>q;
	for(int i = 0 ; i < n ; i++){
		char c;
		int h;
		cin>>c;
		if(c == 'J'){
			h = 0;
		} else if(c == 'O'){
			h = 1;
		} else {
			h = 2;
		}
		a[f[i]].push_back(h);
		v[f[i]].push_back(i);
	}
	for(int k = 0 ; k < 27 ; k++){
		vs[k] = sze(v[k]);
		lb[k][n] = vs[k];
		for(int i = n - 1 ; ~i ; i--){
			lb[k][i] = lb[k][i + 1];
			lb[k][i] -= (f[i] == k);
		}
	}
	for(int k = 0 ; k < 27 ; k++){
		int sz = vs[k];
		sq[k] = (sz == 0 ? 1 : sqrt(sz));
		for(int i = 0 ; i < sz ; i++){
			cnt[k][i / sq[k]][a[k][i]]++;
			Cnt[k][a[k][i]]++;
		}
	}
	cout<<(check() ? "Yes\n" : "No\n");
	for(int i = 0 ; i < q ; i++){
		int l , r , h;
		char c;
		cin>>l>>r>>c; l--;
		if(c == 'J'){
			h = 0;
		} else if(c == 'O'){
			h = 1;
		} else {
			h = 2;
		}
		for(int k = 0 ; k < 27 ; k++){
			if(v[k].empty()) continue;
			int lk = lb[k][l] , rk = lb[k][r];
//			cout<<k<<' '<<lk<<' '<<rk<<' '<<h<<' '<<Cnt[k][0]<<' '<<Cnt[k][1]<<' '<<Cnt[k][2]<<'\n';
			sett(k , lk , rk , h);
		}
		cout<<(check() ? "Yes\n" : "No\n");
	}
	return 0;
}

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