Submission #419614

#	Time	Username	Problem	Language	Result	Execution time	Memory
419614		Kevin_Zhang_TW	Crossing (JOI21_crossing)	C++17	100 / 100	1648 ms	45660 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;

int n, q;
vector<string> s(3);
string t;

char trans(char a, char b) { if (a == b) return a; return 'J' + 'O' + 'I' - a - b; }

string comb(string a, const string &b) {
	for (int i = 0;i < a.size();++i)
		a[i] = trans(a[i], b[i]);
	return a;
}

string yn(bool t) { return t ? "Yes" : "No"; }

struct sgt {
	int n;
	struct node {
		int sym, bad, tg;
		node () : sym(-1), bad(0), tg(-1) {}
		void operator = (int c) {
			tg = c;
			bad = sym != c;
		}
		node (node a, node b) {
			if (a.sym == b.sym) sym = a.sym;
			else sym = -1;
			bad = a.bad + b.bad;
			tg = -1;
		}
	};
	vector<node> val;
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void push(int i) {
		if (i >= n || val[i].tg == -1) return;
		int &t = val[i].tg;
		val[i<<1] = t, val[i<<1|1] = t;
		t = -1;
	}
	sgt(string s, string t) {
		n = s.size();
		val.resize(n<<1);
		for (int i = 0;i < n;++i) {
			val[i+n].sym = s[i];
			val[i+n] = t[i];
		}
		for (int i = n-1;i > 0;--i) {
			upd(i);
		}
	}
	bool ok() {
		int l = 0, r = n, bad = 0;
		l += n, r += n;
		for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) bad += val[l++].bad;
			if (r&1) bad += val[--r].bad;
		}
		return bad == 0;
	}
	//bool ok() { DE(val[1].bad); return val[1].bad == 0; }
	void modify(int l, int r, int c) {
		int sl = l += n, sr = r += n;
		for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] = c;
			if (r&1) val[--r] = c;
		}
		for (;sl>>=1, sr>>=1;) upd(sl), upd(sr);
	}
};

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (auto &i : s) cin >> i;


	for (int i = 0;i < s.size();++i)
		for (int j = i+1;j < s.size();++j) {
			string x = comb(s[i], s[j]);
			if (!count(AI(s), x))
				s.pb(x);
			assert(s.size() <= 9);
		}


	cin >> q >> t;

	vector<sgt> tree;
	for (int i = 0;i < s.size();++i)
		tree.pb(sgt(s[i], t));

	auto exist = [&]() {
		for (int i = 0;i < s.size();++i)
			if (tree[i].ok()) return true;
		return false;
	};

	cout << yn(exist()) << '\n';

	while (q--) {
		int l, r;
		char c;
		cin >> l >> r >> c; --l;

		for (int i = 0;i < s.size();++i) 
			tree[i].modify(l, r, c);

		cout << yn(exist()) << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In function 'std::string comb(std::string, const string&)':
Main.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0;i < a.size();++i)
      |                 ~~^~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0;i < s.size();++i)
      |                 ~~^~~~~~~~~~
Main.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int j = i+1;j < s.size();++j) {
      |                    ~~^~~~~~~~~~
Main.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for (int i = 0;i < s.size();++i)
      |                 ~~^~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:117:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (int i = 0;i < s.size();++i)
      |                  ~~^~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for (int i = 0;i < s.size();++i)
      |                  ~~^~~~~~~~~~

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