제출 #421890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421890		hhhhaura	Crossing (JOI21_crossing)	C++14	100 / 100	368 ms	22244 KiB

Main

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n, ans, cur; 
	const int C = 37;
	random;
	vector<int> s, c;
	vector<vector<int>> a;
	map<int, int> mp;
	set<int> b;
	int rolling(vector<int> a) {
		int ans = 0;
		rep(i, 1, n) ans = (ans + (c[i] - c[i - 1]) * s[a[i]] % MOD) % MOD;
		return (ans % MOD + MOD) % MOD;
	}
	vector<int> operate(vector<int> a, vector<int> b) {
		vector<int> c(n + 1, 0);
		rep(i, 1, n) {
			if(a[i] == b[i]) c[i] = a[i];
			else if(a[i] != 0 && b[i] != 0) c[i] = 0;
			else if(a[i] != 1 && b[i] != 1) c[i] = 1;
			else c[i] = 2;
		}
		return c;
	}
	void init_(int _n, vector<string> _s) {
		n = _n, ans = 0, cur = 0;
		c.assign(n + 1, 1);
		s.assign(3, 0);
		a.assign(4, vector<int>(n + 1, 0));
		mp.clear();
		rep(i, 0, 2) s[i] = rnd();
		rep(i, 1, n) {
			rep(j, 0, 3) {
				if(_s[j][i - 1] == 'J') a[j][i] = 0;
				else if(_s[j][i - 1] == 'O') a[j][i] = 1;
				else a[j][i] = 2;
			}
			c[i] = c[i - 1] * C % MOD;
		}
		rep(i, 1, n) c[i] = (c[i - 1] + c[i]) % MOD;
		rep(i, 0, 2) b.insert(rolling(a[i]));
		b.insert(rolling(operate(a[0], a[1])));
		b.insert(rolling(operate(a[0], a[2])));
		b.insert(rolling(operate(a[2], a[1])));
		b.insert(rolling(operate(operate(a[0], a[1]), a[2])));
		b.insert(rolling(operate(operate(a[0], a[2]), a[1])));
		b.insert(rolling(operate(operate(a[2], a[1]), a[0])));
		cur = rolling(a[3]);
		ans = bool(b.find(cur) != b.end());
		rep(i, 1, n) mp[i] = a[3][i];
		mp[n + 1] = -1;
		
		return;
	}
	bool query(int L, int R, int x) {
		auto it = mp.upper_bound(L);
		auto temp = it, pre = it;
		bool yes = 1;
		if(pre != mp.begin()) {
			temp = prev(pre);
			int l = L, r = pre -> first - 1;
			if(r >= R) {
				cur -= (c[R] - c[l - 1]) * s[temp -> second] % MOD;
				cur = (cur % MOD + MOD) % MOD;
				if(R + 1 <= r) mp[R + 1] = temp -> second;
				yes = 0;
			}
			else {
				cur -= (c[r] - c[l - 1]) * s[temp -> second] % MOD;
				cur = (cur % MOD + MOD) % MOD;
			}
		}
		while(yes && next(it) != mp.end()) {
			int l = it -> first, r = next(it) -> first - 1;
			if(r >= R) {
				cur -= (c[R] - c[l - 1]) * s[it -> second] % MOD;
				cur = (cur % MOD + MOD) % MOD;
				if(R + 1 <= r) mp[R + 1] = it -> second;
				mp.erase(it);
				break;
			}
			else {
				cur -= (c[r] - c[l - 1]) * s[it -> second] % MOD;
				cur = (cur % MOD + MOD) % MOD;
				temp = it;
				it = next(it);
				mp.erase(temp);
			}
		}
		
		mp[L] = x;
		cur += (c[R] - c[L - 1]) * s[x] % MOD;
		cur = (cur % MOD + MOD) % MOD;
		return b.find(cur) != b.end();	
	}
}; 
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q; cin >> n;
	vector<string> s(4, "");
	rep(i, 0, 2) cin >> s[i];
	cin >> q >> s[3];
	init_(n, s);
	if(ans) cout << "Yes\n";
	else cout << "No\n";
	rep(i, 1, q) {
		int L, R, x; char cc;
		cin >> L >> R >> cc; 
		if(cc == 'J') x = 0;
		else if(cc == 'O') x = 1;
		else x = 2;
		if(query(L, R, x)) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}  

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

Main.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
Main.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
Main.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

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