제출 #1223110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223110		trideser	Crossing (JOI21_crossing)	C++20	26 / 100	357 ms	11216 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;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, Q;
	cin >> N;
	string s, t;
	cin >> s;
	cin >> s;
	cin >> s;
	cin >> Q;
	cin >> t;
	
	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;
		}
	}


/*
	for(vector<int> v : p) {
		for(int a : v)
			cout << a << " ";
		cout << "\n";
	}
	cout << "\n";
*/

	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";
	for(int i = 0; i < Q; i++) {
		int a, b;
		char val;
		cin >> a;
		cin >> b;
		cin >> val;
		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;
	//		cout << "+" << j << " " << (vali==j?1:0) << " " << ca << " " << cb << " " << a << " " << b << " " << start << " " << end << "\n";
			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);
	//		cout << j << " " << forest[j].size << " " << curc[j] - 1 << " " << forest[j].get(0, curc[j] - 1) << "\n";
			//forest[j].print();
		}
		cout << (sum == N ? "Yes" : "No") << "\n";
	}
}

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