Submission #540103

#	Time	Username	Problem	Language	Result	Execution time	Memory
540103		rk42745417	Crossing (JOI21_crossing)	C++17	100 / 100	345 ms	20036 KiB

Main

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 2e5 + 25, C = 48763;
struct segtree {
	ll fac[N], sum[N], arr[N << 2], tag[N << 2];
	int n;
	void init(int _n) { 
		n = _n;
		fac[0] = sum[0] = 1;
		for(int i = 1; i <= n; i++) {
			fac[i] = fac[i - 1] * C % MOD;
			sum[i] = (sum[i - 1] + fac[i]) % MOD;
		}
	}

	void build(int l, int r, int id, string &s) {
		if(l == r - 1) {
			arr[id] = s[l] * fac[l] % MOD;
			return;
		}
		int m = l + r >> 1;
		build(l, m, id << 1, s);
		build(m, r, id << 1 | 1, s);
		arr[id] = (arr[id << 1] + arr[id << 1 | 1]) % MOD;
	};
	inline void build(string &s) { build(0, n, 1, s); }

	inline ll que_sum(int l, int r) {
		if(!l)
			return sum[r - 1];
		return (sum[r - 1] - sum[l - 1] + MOD) % MOD;
	}
	inline void upd(int id, int l, int r, char c) {
		tag[id] = c;
		arr[id] = c * que_sum(l, r) % MOD;
	}
	inline void push(int id, int l, int r) {
		if(!tag[id])
			return;
		int m = l + r >> 1;
		upd(id << 1, l, m, tag[id]);
		upd(id << 1 | 1, m, r, tag[id]);
		tag[id] = 0;
	}

	void edt(int l, int r, int id, int ql, int qr, char c) {
		if(r <= ql || qr <= l)
			return;
		if(ql <= l && r <= qr) {
			upd(id, l, r, c);
			return;
		}
		push(id, l, r);
		int m = l + r >> 1;
		edt(l, m, id << 1, ql, qr, c);
		edt(m, r, id << 1 | 1, ql, qr, c);
		arr[id] = (arr[id << 1] + arr[id << 1 | 1]) % MOD;
	}
	inline void edt(int l, int r, char c) { edt(0, n, 1, l, r, c); }

	inline ll que() { return arr[1]; }
} tree;

signed main() {
	int n;
	cin >> n;
	tree.init(n);
	string arr[3];
	for(int i = 0; i < 3; i++)
		cin >> arr[i];

	const string tmp = "JOI";
	auto solve = [&](auto a, auto b) {
		string res(n, 'a');
		for(int i = 0; i < n; i++) {
			if(a[i] == b[i])
				res[i] = a[i];
			else {
				int it = 0;
				while(tmp[it] == a[i] || tmp[it] == b[i])
					it++;
				res[i] = tmp[it];
			}
		}
		return res;
	};

	vector<int> ord = {0, 1, 2};
	vector<string> owo;
	for(int i = 0; i < 3; i++)
		owo.push_back(arr[i]);
	do {
		if(ord[0] < ord[1])
			owo.push_back(solve(arr[ord[0]], arr[ord[1]]));
		owo.push_back(solve(solve(arr[ord[0]], arr[ord[1]]), arr[ord[2]]));
	} while(next_permutation(ord.begin(), ord.end()));

	set<int> has;
	for(auto x : owo) {
		tree.build(x);
		has.insert(tree.que());
	}

	auto test = [&]() {
		return has.count(tree.que());
	};

	int q;
	cin >> q;
	string s;
	cin >> s;
	tree.build(s);
	cout << (test() ? "Yes" : "No") << '\n';
	while(q--) {
		int l, r;
		char c;
		cin >> l >> r >> c;
		tree.edt(l - 1, r, c);
		cout << (test() ? "Yes" : "No") << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(int, int, int, std::string&)':
Main.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'void segtree::push(int, int, int)':
Main.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'void segtree::edt(int, int, int, int, int, char)':
Main.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int m = l + r >> 1;
      |           ~~^~~

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