Submission #1223481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223481		trideser	Crossing (JOI21_crossing)	C++20	100 / 100	437 ms	11284 KiB

Main

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

#define mod 0x7fffffff

struct SegmentTree {
	vector<long long> hash;
	vector<char> upd;
	int size;
	int depth;
	int constant;
	vector<long long> powers;
	vector<long long> powers_prefix;
	SegmentTree(int N, vector<char> vec, int a) {
		size = 1;
		depth = 0;
		constant = a;
		while(size < N) {
			size *= 2;
			depth++;
		}
		powers = vector<long long>(N);
		powers_prefix = vector<long long>(N);
		powers[0] = 1;
		powers_prefix[0] = 1;
		for(int i = 1; i < N; i++) {
			powers[i] = (powers[i - 1] * constant) % mod;
			powers_prefix[i] = (powers_prefix[i - 1] + powers[i]) % mod;
		}

		hash = vector<long long>(2 * size);
		upd = vector<char>(2 * size, 0);
		long long curhash = 0;
		for(int i = 0; i < vec.size(); i++) {
			curhash = (powers[i] * vec[i]) % mod;
			hash[size + i] = curhash;
		}
		for(int i = depth - 1; i >= 0; i--) {
			for(int j = 0; j < (1 << i); j++) {
				int node = (1 << i) + j;
				hash[node] = (hash[2 * node] + hash[2 * node + 1]) % mod;
			}
		}
	}
	long long pref(int a, int b) {
		return ((powers_prefix[b] - (a == 0 ? 0 : powers_prefix[a - 1])) % mod + mod) % mod;
	}
	void propagate(int node, int d) {
		if(upd[node] == 0x0)
			return;
		int index = node - (1 << d);
		if(d != depth) {
			upd[2 * node] = upd[node];
			upd[2 * node + 1] = upd[node];
			//cout << "C";
		}
		hash[node] = (pref((1 << (depth - d)) * index, (1 << (depth - d)) * (index + 1) - 1) * upd[node]) % mod;
		//cout << "P: " << node << " " << d << " " << (1 << depth - d) * index << " " << (1 << (depth - d)) * (index + 1) - 1 << "\n";
		upd[node] = 0x0;
	}
	void set(int begin, int end, char ch) {
		int a = 0;
		int b = 0;
		for(int i = 0; i < depth; i++) {
			int layersize = (1 << (depth - i));
			int aindex = (1 << i) + a;
			int bindex = (1 << i) + b;
			int na, nb;
			//cout << a << " " << b << " " << a * layersize + layersize / 2 << " " << b * layersize + layersize / 2<< "\n";
			propagate(aindex, i);
			propagate(bindex, i);
			if(a * layersize + layersize / 2 <= begin) {
				//cout << "r";
				// branch right
				na = 2 * a + 1;
			}
			else {
				//cout << "l";
				// branch left
				na = 2 * a;
				if(a != b) {
					upd[aindex * 2 + 1] = ch;
				}
			}
			if(b * layersize + layersize / 2 <= end) {
				//cout << "r";
				// branch right
				nb = 2 * b + 1;
				if(a != b) {
					upd[bindex * 2] = ch;
				}
			}
			else {
				//cout << "l";
				// branch left
				nb = 2 * b;
			}
			//cout << "\n";
			a = na;
			b = nb;
		}
		int aindex = (1 << depth) + a;
		int bindex = (1 << depth) + b;
		upd[aindex] = ch;
		upd[bindex] = ch;
		propagate(aindex, depth);
		propagate(bindex, depth);
		aindex /= 2;
		bindex /= 2;
		for(int i = depth - 1; i >= 0; i--) {
			propagate(aindex, i);
			propagate(2 * aindex, i + 1);
			propagate(2 * aindex + 1, i + 1);
			hash[aindex] = (hash[2 * aindex] + hash[2 * aindex + 1]) % mod;

			propagate(bindex, i);
			propagate(2 * bindex, i + 1);
			propagate(2 * bindex + 1, i + 1);
			hash[bindex] = (hash[2 * bindex] + hash[2 * bindex + 1]) % mod;

			aindex /= 2;
			bindex /= 2;
		}
	}
	long long get(int begin, int end) {
		int a = 0;
		int b = 0;
		long long ret = 0;
		for(int i = 0; i < depth; i++) {
			int layersize = (1 << (depth - i));
			int aindex = (1 << i) + a;
			int bindex = (1 << i) + b;
			int na, nb;
			//cout << a << " " << b << " " << a * layersize + layersize / 2 << " " << b * layersize + layersize / 2<< "\n";
			propagate(aindex, i);
			propagate(bindex, i);
			if(a * layersize + layersize / 2 <= begin) {
				//cout << "r";
				// branch right
				na = 2 * a + 1;
			}
			else {
				//cout << "l";
				// branch left
				na = 2 * a;
				if(a != b) {
					propagate(aindex * 2 + 1, i + 1);
					ret += hash[aindex * 2 + 1];
				}
			}
			if(b * layersize + layersize / 2 <= end) {
				//cout << "r";
				// branch right
				nb = 2 * b + 1;
				if(a != b) {
					propagate(bindex * 2, i + 1);
					ret += hash[bindex * 2];
				}
			}
			else {
				//cout << "l";
				// branch left
				nb = 2 * b;
			}
			//cout << "\n";
			a = na;
			b = nb;
		}

		int aindex = (1 << depth) + a;
		int bindex = (1 << depth) + b;
		propagate(aindex, depth);
		propagate(bindex, depth);
		ret += hash[aindex];
		if(a != b)
			ret += hash[bindex];

		return ret % mod;
	}
	void print() {
		//cout << "TREE:\n";
		for(int i = 0; i <= depth; i++) {
			for(int j = 0; j < (1 << i); j++) {
				//cout << hash[(1 << i) + j] << " ";
			}
			//cout << "\n";
		}
		//cout << "\n";
		for(int i = 0; i <= depth; i++) {
			for(int j = 0; j < (1 << i); j++) {
				//cout << (upd[(1 << i) + j] == 0x0 ? '-' : upd[(1 << i) + j]) << " ";
			}
			//cout << "\n";
		}
		//cout << "----------\n";
	}
};

string cross(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;
}
long long hashs(string& s, int a) {
	long long pow = 1;
	long long ret = 0;
	for(int i = 0; i < s.size(); i++) {
		ret = (ret + (pow * s[i])) % mod;
		pow = (pow * a) % mod;
	}
	return ret;
}
int main() {
	int N, Q;
	vector<string> vect(9);
	cin >> N;
	cin >> vect[0];
	cin >> vect[1];
	cin >> vect[2];
	vect[3] = cross(vect[0], vect[1]);
	vect[4] = cross(vect[0], vect[2]);
	vect[5] = cross(vect[1], vect[2]);
	vect[6] = cross(vect[3], vect[2]);
	vect[7] = cross(vect[4], vect[1]);
	vect[8] = cross(vect[5], vect[0]);
	cin >> Q;
	string ff;
	cin >> ff;
	vector<char> start(N);
	//cout << ff;
	for(int i = 0; i < N; i++) {
		start[i] = ff[i];
	}
	unordered_set<long long> hashes;
	for(string s : vect) {
		hashes.insert(hashs(s, 31));
	}
	SegmentTree tree(N, start, 31);
	long long ret = tree.get(0, N - 1);
	cout << (hashes.find(ret) == hashes.end() ? "No" : "Yes") << "\n";
	for(int i = 0; i < Q; i++) {
		int a, b;
		char ch;
		cin >> a;
		cin >> b;
		cin >> ch;
		a--;
		b--;
		tree.set(a, b, ch);
		long long ret = tree.get(0, N - 1);
		cout << (hashes.find(ret) == hashes.end() ? "No" : "Yes") << "\n";
	}
	return 0;
}

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