Submission #1192110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192110		Kel_Mahmut	Crossing (JOI21_crossing)	C++20	0 / 100	270 ms	3324 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
typedef long long ll;

using namespace std;

int main(){
	int n, q;
	string A, B, C, T;
	cin >> n >> A >> B >> C;
	cin >> q >> T;
	vector<array<int, 3>> u(q);
	for(int i = 0; i < q; i++){
		char c;
		cin >> u[i][0] >> u[i][1] >> c;
		u[i][0]--; u[i][1]--;
		u[i][2] = (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
	}
	auto to_int = [&](string & x){
		vector<int> ret(n);
		for(int i = 0; i < n; i++){
			ret[i] = (x[i] == 'J' ? 0 : (x[i] == 'O' ? 1 : 2));
		}
		return ret;
	};
	vector<int> t = to_int(T);
	auto op = [&](vector<int> & x, vector<int> & y){
		vector<int> ret(n);
		for(int i = 0; i < n; i++){
			if(x[i] == y[i]) ret[i] = x[i];
			else ret[i] = 3 - x[i] - y[i];
		}
		return ret;
	};
	vector<vector<int>> f(9);
	f[0] = to_int(A); 		f[1] = to_int(B);		f[2] = to_int(C);
	f[3] = op(f[0], f[1]); 	f[4] = op(f[0], f[2]); 	f[5] = op(f[1], f[2]);
	f[6] = op(f[3], f[2]); 	f[7] = op(f[4], f[1]); 	f[8] = op(f[5], f[0]);

	auto to_set = [&](vector<int> & x){
		set<pair<int, int>> y;
		int beg = 0;
		for(int i = 0; i < n; i++){
			if(i + 1 == n || x[i] != x[i + 1]){
				y.insert({beg, x[i]});
				beg = i + 1;
			}
		}
		return y;
	};

	vector<int> cnt(9);
	vector<set<pair<int, int>>> s(9);
	for(int i = 0; i < 9; i++) s[i] = to_set(f[i]);

	set<pair<int, int>> cur;
	function<void(int, int)> erase = [&](int sta, int val){
		assert(cur.find({sta, val}) != cur.end());
		cur.erase({sta, val});
		for(int i = 0; i < 9; i++){
			if(s[i].find({sta, val}) != s[i].end()) cnt[i]--;
		}
		auto it = cur.lower_bound({sta, val});
		if(it != cur.end() && it != cur.begin()){
			if(prev(it)->second == it->second){
				erase(it->first, it->second);
			}
		}
	};

	auto insert = [&](int sta, int val){
		cur.insert({sta, val});
		for(int i = 0; i < 9; i++){
			if(s[i].find({sta, val}) != s[i].end()) cnt[i]++;
		}
		auto it = cur.find({sta, val});
		if(next(it) != cur.end()){
			if(it->second == next(it)->second){
				erase(next(it)->first, next(it)->second);
			}
		}
		it = cur.find({sta, val});
		if(it != cur.begin()){
			if(prev(it)->second == it->second){
				erase(it->first, it->second);
			}
		}
	};

	auto fine = [&](){
		bool ok = 0;
		for(int i = 0; i < 9; i++){
			if(cnt[i] == (int)s[i].size() && cnt[i] == (int) cur.size()) ok = 1;
		}
		return ok;
	};

	auto print = [&](set<pair<int, int>> &s){
		for(auto [x, y] : s){
			cout << x << ' ' << y << endl;
		}
		cout << endl;
	};

	int beg = 0;
	for(int i = 0; i < n; i++){
		if(i + 1 == n || t[i] != t[i + 1]){
			insert(beg, t[i]);
			beg = i + 1;
		}
	}

	// for(int i = 0; i < 9; i++){
	// 	cout << "printing " << i << endl;
	// 	print(s[i]);
	// }
	// cout << "printing t" << endl;
	// print(cur);

	cout << (fine() ? "Yes" : "No") << endl;
	for(int i = 0; i < q; i++){
		int ql = u[i][0];
		int qr = u[i][1];
		int val = u[i][2];

		int son = prev(cur.upper_bound({qr + 1, 2}))->second;

		while(cur.lower_bound({ql, 0}) != cur.end() && cur.lower_bound({ql, 0})->first <= qr){
			auto it = cur.lower_bound({ql, 0});
			erase(it->first, it->second);
		}
		insert(ql, val);
		if(qr + 1 < n){
			if(cur.lower_bound({qr + 1, 0}) == cur.end() || cur.lower_bound({qr + 1, 0})->first > qr + 1)
				insert(qr + 1, son);
		}
		cout << (fine() ? "Yes" : "No") << endl;
		// cout << "printing t" << endl;
		// cout << cnt[2] << endl;
		// print(cur);
	}
}

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