Submission #1264841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264841		mingga	Crossing (JOI21_crossing)	C++20	100 / 100	1150 ms	19156 KiB

Main

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 2e5 + 7;
int n, q, id[100];
char d[] = {'J', 'O', 'I'};
string s[3], t, a[10];
bool ans[N];


string combine(string s, string t) {
	string ans = "";
	for(int i = 0; i < n; i++) {
		ans += d[(id[t[i]] * 2 + id[s[i]] * 2) % 3];
	}
	return ans;
}

struct query {
	int l, r;
	char c;
} que[N];

struct SEGTREE {
	struct node {
		int val;
		bool ok;
		node(int v = -1, bool o = 0) {
			val = v;
			ok = o;
		}
		node operator + (const node& o) {
			node ans;
			if(val == o.val) ans.val = val;
			else ans.val = -1;
			ans.ok = ok && o.ok;
			return ans;
		}
	};
	vector<node> st;
	vector<int> lazy, dak;
	SEGTREE(int n, int id) {
		st.resize(n * 4 + 4, node());
		lazy.resize(n * 4 + 4, -1);
		dak.resize(n * 4 + 4, -1);
		build(1, 1, n, id);
	}
	void build(int i, int l, int r, int x) {
		if(l == r) {
			st[i] = node(id[t[l - 1]], a[x][l - 1] == t[l - 1]);
			// cerr << l << ' ' << t[l - 1] << ' ' << a[x][l - 1] << ' ' << st[i].ok << ln;
			dak[i] = id[a[x][l - 1]];
			return;
		}
		int m = (l + r) >> 1;
		build(i * 2, l, m, x);
		build(i * 2 + 1, m + 1, r, x);
		st[i] = st[i * 2] + st[i * 2 + 1];
		if(dak[i * 2] == dak[i * 2 + 1]) dak[i] = dak[i * 2];
		else dak[i] = -1;
		// cerr << i << ' ' << l << ' ' << r << ' ' << dak[i] << ' ' << st[i].ok << ln;
	}
	void push(int i) {
		if(lazy[i] > -1) {
			int x = lazy[i];
			lazy[i] = -1;
			lazy[i * 2] = lazy[i * 2 + 1] = x;
			st[i * 2].val = x;
			if(dak[i * 2] == x) st[i * 2].ok = 1;
			else st[i * 2].ok = 0;
			st[i * 2 + 1].val = x;
			if(dak[i * 2 + 1] == x) st[i * 2 + 1].ok = 1;
			else st[i * 2 + 1].ok = 0;
		}
	}
	void update(int i, int l, int r, int u, int v, int x) {
		if(l > v or r < u) return;
		if(u <= l and r <= v) {
			st[i].val = x;
			lazy[i] = x;
			if(dak[i] == x) st[i].ok = 1;
			else st[i].ok = 0;
			return;
		}
		int m = (l + r) >> 1;
		push(i);
		update(i * 2, l, m, u, v, x);
		update(i * 2 + 1, m + 1, r, u, v, x);
		st[i] = st[i * 2] + st[i * 2 + 1];
		if(dak[i * 2] == dak[i * 2 + 1]) dak[i] = dak[i * 2];
		else dak[i] = -1;
	}
};

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	id['J'] = 0;
	id['O'] = 1;
	id['I'] = 2;
	cin >> n;
	for(int i = 0; i < 3; i++) cin >> s[i];
	cin >> q;
	cin >> t;
	for(int i = 1; i <= q; i++) {
		int l, r;
		char c;
		cin >> l >> r >> c;
		que[i] = {l, r, c};
	}
	int cnt = 0;
	for(int i = 0; i < 3; i++) {
		a[cnt++] = s[i];
		for(int j = i + 1; j < 3; j++) {
			a[cnt++] = combine(s[i], s[j]);
		}
		a[cnt++] = combine(s[i], combine(s[(i + 1)  % 3], s[(i + 2) % 3]));
	}
	for(int i = 0; i < cnt; i++) {
		// cerr << i << ' ' << a[i] << ' ' << t << ln;
		SEGTREE st(n, i);
		if(st.st[1].ok) ans[0] = 1;
		for(int j = 1; j <= q; j++) {
			auto [l, r, c] = que[j];
			st.update(1, 1, n, l, r, id[c]);
			ans[j] |= st.st[1].ok;
		}
	}
	for(int i = 0; i <= q; i++) {
		if(ans[i]) cout << "Yes";
		else cout << "No";
		cout << ln;
	}
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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