Submission #1223122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223122		trideser	Crossing (JOI21_crossing)	C++20	100 / 100	2649 ms	15280 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
	vector<int> data;
	vector<int> upd;
	int size;
	int depth;
	SegmentTree(int N, vector<int> v) {
		size = 1;
		depth = 0;
		while(size < N) {
			size *= 2;
			depth++;
		}
		data = vector<int>(2 * size, 0);
		upd = vector<int>(2 * size, -1);
		for(int i = 0; i < v.size(); i++) {
			data[size + i] = v[i];
		}
		for(int i = depth - 1; i >= 0; i--) {
			for(int j = 0; j < (1 << i); j++) {
				int node = (1 << i) + j;
				data[node] = data[2 * node] + data[2 * node + 1];
			}
		}
	}

	void propagate(int node, int layer) {
		if(upd[node] == -1)
			return;
		if(layer != depth) {
			upd[2 * node] = upd[node];
			upd[2 * node + 1] = upd[node];
		}
		data[node] = (upd[node] << (depth - layer));
		upd[node] = -1;
	}

	void set(int begin, int end, int val) {
		int a = 0;
		int b = 0;
		for(int i = 0; i < depth; i++) {
			int na, nb;
			int aindex = a + (1 << i);
			int bindex = b + (1 << i);
			propagate(aindex, i);
			propagate(bindex, i);
			if((a << (depth - i)) + (1 << (depth - i - 1)) <= begin) {
				na = 2 * a + 1;
			}
			else {
				if(a != b) {
					propagate(2 * aindex + 1, i + 1);
					upd[2 * aindex + 1] = val;
				}
				na = 2 * a;
			}

			if((b << (depth - i)) + (1 << (depth - i - 1)) - 1 >= end) {
				nb = 2 * b;
			}
			else {
				if(a != b) {
					propagate(2 * bindex, i + 1);
					upd[2 * bindex] = val;
				}
				nb = 2 * b + 1;
			}
			a = na;
			b = nb;
		}
		int aindex = a + (1 << depth);
		int bindex = b + (1 << depth);
		propagate(aindex, depth);
		propagate(bindex, depth);
		upd[aindex] = val;
		upd[bindex] = val;

		aindex /= 2;
		bindex /= 2;
		for(int i = depth - 1; i >= 0; i--) {
			propagate(2 * aindex, i + 1);
			propagate(2 * aindex + 1, i + 1);
			propagate(2 * bindex, i + 1);
			propagate(2 * bindex + 1, i + 1);
			data[aindex] = data[2 * aindex] + data[2 * aindex + 1];
			data[bindex] = data[2 * bindex] + data[2 * bindex + 1];
			aindex /= 2;
			bindex /= 2;
		}
	}

	int get(int begin, int end) {
		int a = 0;
		int b = 0;
		int ret = 0;
		for(int i = 0; i < depth; i++) {
			int na, nb;
			int aindex = a + (1 << i);
			int bindex = b + (1 << i);
			if((a << (depth - i)) + (1 << (depth - i - 1)) <= begin) {
				na = 2 * a + 1;
			}
			else {
				if(a != b) {
					propagate(2 * aindex + 1, i + 1);
					ret += data[2 * aindex + 1];
				}
				na = 2 * a;
			}

			if((b << (depth - i)) + (1 << (depth - i - 1)) - 1 >= end) {
				nb = 2 * b;
			}
			else {
				if(a != b) {
					propagate(2 * bindex, i + 1);
					ret += data[2 * bindex];
				}
				nb = 2 * b + 1;
			}
			a = na;
			b = nb;
		}
		int aindex = a + (1 << depth);
		int bindex = b + (1 << depth);
		propagate(aindex, depth);
		propagate(bindex, depth);
		ret += data[aindex];
		if(aindex != bindex) ret += data[bindex];
		return ret;
	}
	void print() {
		cout << "TREE:\n";
		for(int a : data)
			cout << a << " ";
		cout << "\n";
		for(int a : upd)
			cout<<a<<" ";
		cout << "\n\n";
	}
};

int chti(char ch) {
	if (ch == 'J') return 0;
	if (ch == 'O') return 1;
	if (ch == 'I') return 2;
	return -1;
}

void solve(int N, int Q, string& s, string& t, vector<bool>& result, vector<tuple<int, int, char>>& input) {
	vector<vector<int>> vect(3, vector<int>(N));
	vector<int> curc(3, 0);
	for(int i = 0; i < N; i++) {
		curc[chti(s[i])]++;
		for(int j = 0; j < 3; j++)
			vect[j][i] = curc[j];
	}
	
	vector<vector<int>> p(3);
	for(int i = 0; i < 3; i++) {
		p[i] = vector<int>(curc[i] + 3, 0);
	}
	for(int i = 0; i < N; i++) {
		if(s[i] == t[i]) {
			p[chti(s[i])][vect[chti(s[i])][i] - 1] = 1;
		}
	}

	vector<SegmentTree> forest;
	for(int i = 0; i < 3; i++) {
		forest.push_back(SegmentTree(curc[i] + 3, p[i]));
	}

	int sum = 0;
	for(int j = 0; j < 3; j++) {
		sum += forest[j].get(0, curc[j] - 1);
	}
	//cout << (sum == N ? "Yes" : "No") << "\n";
	if(sum == N)
		result[0] = true;
	for(int i = 0; i < Q; i++) {
		int a, b;
		char val;
		a = get<0>(input[i]);
		b = get<1>(input[i]);
		val = get<2>(input[i]);
		a--;
		b--;
		int vali = chti(val);

		for(int j = 0; j < 3; j++) {
			int ca = a == 0 ? 0 : vect[j][a - 1];
			int cb = vect[j][b];
			if(cb - ca == 0)
				continue;
			int start = ca;
			int end = cb - 1;
			forest[j].set(start, end, vali == j ? 1 : 0);
		}
		int sum = 0;
		for(int j = 0; j < 3; j++) {
			sum += forest[j].get(0, curc[j] - 1);
		}
		if(sum == N)
			result[i + 1] = true;
		//cout << (sum == N ? "Yes" : "No") << "\n";
	}
}

string crossing(string& a, string& b) {
	string ret = a;
	for(int i = 0; i < a.size(); i++) {
		if(a[i] == b[i])
			ret[i] = a[i];
		else if(a[i] != 'J' && b[i] != 'J')
			ret[i] = 'J';
		else if(a[i] != 'O' && b[i] != 'O')
			ret[i] = 'O';
		else if(a[i] != 'I' && b[i] != 'I')
			ret[i] = 'I';
	}
	return ret;
}

int main() {
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	int N, Q;
	cin >> N;
	string s, t;
	vector<string> genes;
	cin >> s;
	genes.push_back(s);
	cin >> s;
	genes.push_back(s);
	cin >> s;
	genes.push_back(s);
	genes.push_back(crossing(genes[0], genes[1]));
	genes.push_back(crossing(genes[0], genes[2]));
	genes.push_back(crossing(genes[1], genes[2]));
	genes.push_back(crossing(genes[3], genes[2]));
	genes.push_back(crossing(genes[4], genes[1]));
	genes.push_back(crossing(genes[5], genes[0]));

	cin >> Q;
	cin >> t;
	vector<bool> result(Q + 1, false);
	vector<tuple<int, int, char>> input(Q);
	for(int i = 0; i < Q; i++) {
		int a, b;
		char ch;
		cin >> a;
		cin >> b;
		cin >> ch;

		input[i] = make_tuple(a, b, ch);
	}
	for(int i = 0; i < 9; i++) {
		solve(N, Q, genes[i], t, result, input);
	}
	for(bool b : result)
		cout << (b ? "Yes" : "No") << "\n";
	return 0;
}

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