Submission #1192078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192078		Kel_Mahmut	Crossing (JOI21_crossing)	C++20	0 / 100	124 ms	3140 KiB

Main

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

using namespace std;

int main(){
	int n, q;
	cin >> n;
	string T;
	vector<string> S(3);
	cin >> S[0] >> S[1] >> S[2];
	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);
	}
	vector<int> t(n);
	vector<vector<int>> s(3, vector<int>(n));
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < n; j++){
			s[i][j] = (S[i][j] == 'J' ? 0 : S[i][j] == 'O' ? 1 : 2);
		}
	}
	for(int i = 0; i < n; i++)
		t[i] = (T[i] == 'J' ? 0 : T[i] == 'O' ? 1 : 2);

	set<array<int, 2>> a, b;
	int beg = 0;
	for(int i = 0; i < n; i++){
		if(i + 1 == n || s[0][i] != s[0][i + 1]){
			a.insert({beg, s[0][i]});
			beg = i + 1;
		}
	}

	int ans = 0;
	function<void(int, int)> del = [&](int sta, int val){
		assert(b.find({sta, val}) != b.end());
		if(a.find({sta, val}) != a.end()){
			ans--;
		}
		b.erase({sta, val});
		auto it = b.lower_bound({sta, val});
		if(it != b.end() && it != b.begin() && (*prev(it))[1] == (*it)[1]){
			del((*it)[0], (*it)[1]);
		};
	};
	auto add = [&](int sta, int val){
		auto it = b.upper_bound({sta, val});
		if(it != b.begin() && (*prev(it))[1] == val){
			return;
		}
		b.insert({sta, val});
		if(a.find({sta, val}) != a.end()){
			ans++;
		}
		it = b.upper_bound({sta, val});
		if(it != b.end() && (*it)[1] == val){
			del((*it)[0], (*it)[1]);
		}
	};
	// auto print = [&](set<array<int, 2>> A){
	// 	for(auto [sta, val] : A) cout << sta << ' ' << val << endl;
	// 	cout << endl;
	// };
	beg = 0;
	for(int i = 0; i < n; i++){
		if(i + 1 == n || t[i] != t[i + 1]){
			add(beg, t[i]);
			beg = i + 1;
		}
	}
	// cout << "printing a: " << endl;
	// print(a);
	// cout << "printing b: " << endl;
	// print(b);
	cout << (ans == (int) a.size() ? "Yes" : "No") << endl;
	// cout << ans << endl;
	for(int i = 0; i < q; i++){
		int ql = u[i][0];
		int qr = u[i][1];
		int x = u[i][2];
		array<int, 2> lst = {-1, -1};
		while(b.lower_bound({ql, 0}) != b.end() && (*b.lower_bound({ql, 0}))[0] <= qr){
			auto it = b.lower_bound({ql, 0});
			lst = *it;
			del(lst[0], lst[1]);
		}
		if(lst[0] == -1){
			assert(b.lower_bound({ql, 0}) != b.begin());
			lst = *prev(b.lower_bound({ql, 0}));

		}
		if(b.lower_bound({ql, 0}) != b.end() && (*b.lower_bound({ql, 0}))[0] > qr + 1){
			add(qr + 1, lst[1]);
		}
		add(ql, x);
		cout << (ans == (int) a.size() ? "Yes" : "No") << endl;
		// cout << ans << endl;
		// cout << "printing b" << endl;
		// print(b);
	}
}

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