제출 #528753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528753		d2k05	Crossing (JOI21_crossing)	C++14	100 / 100	949 ms	15176 KiB

Main

#include <bits/stdc++.h>

#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);

using namespace std;
using ll = long long;

const int mxN = 2e5 + 5, mod = 1e9 + 7, p = 31;

int n, h[3][mxN];
string s[3];
int t[mxN * 4];
char Mod[mxN * 4];
string A;

int binpow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1)
			ans = ans * 1ll * a % mod;
		a = a * 1ll * a % mod;
		b >>= 1;
	}
	return ans;
}

void Build(int v = 1, int tl = 1, int tr = n) {
	Mod[v] = '#';
	if (tl == tr) {
		t[v] = A[tl - 1];
		return;
	}
	int tm = (tl + tr) / 2;
	Build(v * 2, tl, tm);
	Build(v * 2 + 1, tm + 1, tr);
	int sz = tr - tm;
	t[v] = (t[v * 2] * 1ll * binpow(p, sz) % mod + t[v * 2 + 1]) % mod;
}

void Push(int v, int tl, int tr) {
	if (Mod[v] != '#') {
		int i = 0;
		if (Mod[v] == 'O')
			i = 1;
		else if (Mod[v] == 'I') 
			i = 2;
		t[v] = h[i][tr - tl + 1];
		if (tl != tr)
			Mod[v * 2] = Mod[v * 2 + 1] = Mod[v];
		Mod[v] = '#';
	}
}

void Upd(int l, int r, char c, int v = 1, int tl = 1, int tr = n) {
	Push(v, tl, tr);
	if (l > tr || r < tl)
		return;
	if (l <= tl && tr <= r) {
		Mod[v] = c;
		Push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	Upd(l, r, c, v * 2, tl, tm);
	Upd(l, r, c, v * 2 + 1, tm + 1, tr);
	int sz = tr - tm;
	t[v] = (t[v * 2] * 1ll * binpow(p, sz) % mod + t[v * 2 + 1]) % mod;
}

pair <int, int> Get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	Push(v, tl, tr);
	if (l > tr || r < tl)
		return {0, 0};
	if (l <= tl && tr <= r) 
		return {t[v], tr - tl + 1};
	int tm = (tl + tr) / 2;
	auto at = Get(l, r, v * 2, tl, tm);
	int left = at.first, szz = at.second;
	at = Get(l, r, v * 2 + 1, tm + 1, tr);
	int right = at.first, sz = at.second;
	return {(left * 1ll * binpow(p, sz) % mod + right) % mod, szz + sz};
}

int calc(string st) {
	int ans = 0;
	for (int i = 0; i < st.size(); ++i) 
		ans = (ans * 1ll * p % mod + st[i]) % mod;
	return ans;
}

string merge(string a, string b) {
	string ret;
	char sy[3] = {'J', 'O', 'I'};
	for (int i = 0; i < a.size(); ++i) {
		if (a[i] == b[i])
			ret += a[i];
		else {
			for (int j = 0; j < 3; ++j) {
				if (sy[j] != a[i] && sy[j] != b[i])
					ret += sy[j];
			}
		}
	}
	return ret; 
}

int main() {
	fastio;
	cin >> n >> s[0] >> s[1] >> s[2];
	for (int i = 1; i <= n; ++i) {
		h[0][i] = (h[0][i - 1] * 1ll * p % mod + 'J') % mod;
		h[1][i] = (h[1][i - 1] * 1ll * p % mod + 'O') % mod;
		h[2][i] = (h[2][i - 1] * 1ll * p % mod + 'I') % mod;
	}
	set <int> st1;
	set <string> st2;
	for (int i = 0; i < 3; ++i) {
		st1.insert(calc(s[i]));
		st2.insert(s[i]);
	}
	while (true) {
		vector <string> v;
		for (auto x : st2) {
			for (auto y : st2) {
				string nw = merge(x, y);
				if (st2.find(nw) == st2.end()) 
					v.push_back(nw);
			}
		}
		if (v.empty())
			break;
		for (auto x : v)
			st2.insert(x), st1.insert(calc(x));
	} 
	int q;
	cin >> q;
	cin >> A;
	Build(); 
	if (st1.find(Get(1, n).first) != st1.end())
		cout << "Yes\n";
	else
		cout << "No\n";
	while (q--) {
		int l, r;
		cin >> l >> r;
		char c;
		cin >> c;
		Upd(l, r, c);
		if (st1.find(Get(1, n).first) != st1.end())
			cout << "Yes\n";
		else
			cout << "No\n";
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int calc(std::string)':
Main.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < st.size(); ++i)
      |                  ~~^~~~~~~~~~~
Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for (int i = 0; i < a.size(); ++i) {
      |                  ~~^~~~~~~~~~

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