Submission #537633

#	Time	Username	Problem	Language	Result	Execution time	Memory
537633		S2speed	Crossing (JOI21_crossing)	C++17	49 / 100	7034 ms	43432 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 , 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;
}

struct segtree {

	int sz = 1;
	vector<int> val , laz;

	void init(int n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , 0);
		laz.assign(sz << 1 , -1);
		return;
	}

	void shift(int x , int lx , int rx){
		int h = laz[x];
		laz[x] = -1;
		if(h == -1) return;
		val[x] = h * (rx - lx);
		if(rx - lx == 1) return;
		int ln = (x << 1) + 1 , rn = ln + 1;
		laz[ln] = laz[rn] = h;
		return;
	}

	void set(int l , int r , int k , int x , int lx , int rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			laz[x] = k;
			shift(x , lx , rx);
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		set(l , r , k , ln , lx , m); set(l , r , k , rn , m , rx);
		val[x] = val[ln] + val[rn];
		return;
	}

	void set(int l , int r , int k){
		set(l , r , k , 0 , 0 , sz);
	}

};

vector<int> v[27] , a[27];
int f[maxn] , lb[27][maxn];
segtree st[27][3];

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(st[k][0].val[0] > 0 && h[k] != 0){
				res = false;
			}
			if(st[k][1].val[0] > 0 && h[k] != 1){
				res = false;
			}
			if(st[k][2].val[0] > 0 && h[k] != 2){
				res = false;
			}
		}
		if(res) return true;
	}
	return false;
}

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

	memset(f , 0 , sizeof(f));
	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++){
		int vs = sze(v[k]);
		lb[k][n] = vs;
		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 vs = sze(v[k]);
		st[k][0].init(vs); st[k][1].init(vs); st[k][2].init(vs);
		for(int i = 0 ; i < vs ; i++){
			st[k][a[k][i]].set(i , i + 1 , 1);
		}
	}
	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';
			st[k][0].set(lk , rk , h == 0); st[k][1].set(lk , rk , h == 1); st[k][2].set(lk , rk , h == 2);
		}
		cout<<(check() ? "Yes\n" : "No\n");
	}
	return 0;
}

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