Submission #799867

#	Time	Username	Problem	Language	Result	Execution time	Memory
799867		ymm	Crossing (JOI21_crossing)	C++17	100 / 100	181 ms	20692 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

const int N = 200'010;

namespace seg {
	struct node {
		int all[3];
		int eq;
		int lzy;
	} t[4*N];
	int constexpr cnts = 9;
	int sz = 0;

	int to_num(char c) {
		return (c == 'O') + 2*(c == 'I');
	}

	void init(const string s[cnts], const string &t0, int i, int b, int e) {
		if (e-b == 1) {
			Loop (c,0,3) {
				t[i].all[c] = 0;
				Loop (j,0,cnts)
					t[i].all[c] ^= (to_num(s[j][b]) == c) << j;
			}
			t[i].eq = 0;
			Loop (j,0,cnts)
				t[i].eq ^= (s[j][b] == t0[b]) << j;
			t[i].lzy = -1;
			return;
		}
		init(s, t0, 2*i+1, b, (b+e)/2);
		init(s, t0, 2*i+2, (b+e)/2, e);
		Loop (c,0,3)
			t[i].all[c] = t[2*i+1].all[c] & t[2*i+2].all[c];
		t[i].eq = t[2*i+1].eq & t[2*i+2].eq;
		t[i].lzy = -1;
	}
	void init(const string s[cnts], const string &t) {
		sz = t.size();
		init(s, t, 0, 0, sz);
	}

	void tag(int i, int x) {
		t[i].lzy = x;
		t[i].eq = t[i].all[x];
	}

	void ppg(int i) {
		if (t[i].lzy == -1)
			return;
		tag(2*i+1, t[i].lzy);
		tag(2*i+2, t[i].lzy);
		t[i].lzy = -1;
	}

	void up(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r)
			return tag(i, x);
		ppg(i);
		if (l < (b+e)/2)
			up(l, r, x, 2*i+1, b, (b+e)/2);
		if ((b+e)/2 < r)
			up(l, r, x, 2*i+2, (b+e)/2, e);
		t[i].eq = t[2*i+1].eq & t[2*i+2].eq;
	}
	void up(int l, int r, char c) { up(l, r, to_num(c), 0, 0, sz); }
}


string cross(string a, string b)
{
	string ans(a.size(), '\0');
	Loop (i,0,a.size()) {
		if (a[i] == b[i])
			ans[i] = a[i];
		else if ('J' != a[i] && 'J' != b[i])
			ans[i] = 'J';
		else if ('O' != a[i] && 'O' != b[i])
			ans[i] = 'O';
		else if ('I' != a[i] && 'I' != b[i])
			ans[i] = 'I';
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	string a, b, c;
	int n;
	cin >> n >> a >> b >> c;
	vector<string> vec = {a, b, c, cross(a, b), cross(b, c), cross(c, a), cross(cross(a, b), c), cross(cross(b, c), a), cross(cross(c, a), b)};
	string t0;
	int q;
	cin >> q >> t0;
	seg::init(vec.data(), t0);
	cout << (seg::t[0].eq? "Yes\n": "No\n");
	while (q--) {
		int l, r;
		char c;
		cin >> l >> r >> c;
		--l;
		seg::up(l, r, c);
		cout << (seg::t[0].eq? "Yes\n": "No\n");
	}
}

Compilation message (stderr)

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
Main.cpp:76:2: note: in expansion of macro 'Loop'
   76 |  Loop (i,0,a.size()) {
      |  ^~~~

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