제출 #501575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501575		amunduzbaev	Crossing (JOI21_crossing)	C++14	100 / 100	248 ms	19712 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 2e5 + 5;
const int P = 167;
const int mod = (119 << 23) + 1;
int pref[N], pw[N];

struct ST{
	int tree[N * 4], p[N * 4];
	void push(int x, int lx, int rx){
		if(lx == rx || !(~p[x])) return;
		int m = (lx + rx) >> 1;
		tree[x<<1] = p[x] * 1ll * pref[m - lx] % mod, p[x<<1] = p[x];
		tree[x<<1|1] = p[x] * 1ll * pref[rx - m - 1] % mod, p[x<<1|1] = p[x];
		p[x] = -1;
	}
	
	void sett(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] = v * 1ll * pref[rx - lx] % mod;
			p[x] = v; return;
		} push(x, lx, rx);
		int m = (lx + rx) >> 1;
		sett(l, r, v, lx, m, x<<1), sett(l, r, v, m+1, rx, x<<1|1);
		tree[x] = (tree[x<<1] + tree[x<<1|1] * 1ll * pw[m - lx + 1]) % mod;
	}
}tree;

string operator + (string s, string t){
	for(int i=0;i<(int)s.size();i++){
		if(s[i] == t[i]) continue;
		s[i] = 3 - s[i] - t[i];
	} return s;
}

int HH(string t){
	int res = 0;
	for(int i=0;i<(int)t.size();i++){
		res = (res + pw[i] * 1ll * t[i]) % mod;
	} return res;
}

string take(string s){
	for(int i=0;i<(int)s.size();i++){
		if(s[i] == 'J') s[i] = 0;
		if(s[i] == 'O') s[i] = 1;
		if(s[i] == 'I') s[i] = 2;
	} return s;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);

	memset(tree.p, -1, sizeof tree.p);
	pw[0] = pref[0] = 1;
	for(int i=1;i<N;i++){
		pw[i] = pw[i-1] * 1ll * P % mod;
		pref[i] = (pref[i-1] + pw[i]) % mod;
	}
	
	int n; cin>>n;
	string a, b, c; cin>>a>>b>>c;
	//~ cout<<b + c<<"\n";
	a = take(a), b = take(b), c = take(c);
	vector<int> tot;
	tot.push_back(HH(a));
	tot.push_back(HH(b));
	tot.push_back(HH(c));
	tot.push_back(HH(a + b));
	tot.push_back(HH(b + c));
	tot.push_back(HH(a + c));
	tot.push_back(HH((a + c) + b));
	tot.push_back(HH((a + b) + c));
	tot.push_back(HH((b + c) + a));
	
	auto check = [&](){
		int tmp = tree.tree[1];
		//~ cout<<tmp<<" "<<tot[0]<<"\n";
		for(auto x : tot){
			if(x == tmp){
				cout<<"Yes\n";
				return;
			}
		} cout<<"No\n";
	};
	
	int q; cin>>q;
	string s; cin>>s; 
	//~ cout<<s<<"\n";
	s = take(s);
	for(int i=0;i<n;i++) tree.sett(i, i, s[i]);
	check();
	while(q--){
		int l, r; char c; cin>>l>>r>>c, l--, r--;
		if(c == 'J') c = 0;
		if(c == 'O') c = 1;
		if(c == 'I') c = 2;
		tree.sett(l, r, c);
		check();
	}
}

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

Main.cpp: In function 'int main()':
Main.cpp:25:36: warning: array subscript 200005 is above array bounds of 'long long int [200005]' [-Warray-bounds]
   25 |    tree[x] = v * 1ll * pref[rx - lx] % mod;
      |                        ~~~~~~~~~~~~^
Main.cpp:10:5: note: while referencing 'pref'
   10 | int pref[N], pw[N];
      |     ^~~~

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