Submission #436408

#	Time	Username	Problem	Language	Result	Execution time	Memory
436408		Blagojce	Crossing (JOI21_crossing)	C++11	26 / 100	1872 ms	1048580 KiB

Main

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 2e5 + 5;

ll A = 911382323;
ll B = 972663749;


ll pre[3][mxn];


ll seg[4*mxn];
int z[4*mxn];


ll p[mxn];


char alp[3] = {'O', 'I', 'J'};
void upd(int k, int l, int r){
	if(z[k] != 0){
		seg[k] = pre[z[k]-1][r-l+1];
	}
	else{
		int mid = (l+r)/2;
		seg[k] = (((seg[k*2] * p[r-mid]) % B) + seg[k*2+1])%B;
	}
}

void push(int k){
	if(z[k] == 0) return;
	z[k*2] = z[k*2+1] = z[k];
	z[k] = 0;
}

void update(int k, int l, int r, int x, int y, int c){
	if(r < x || l < y){
		if(z[k] != 0) upd(k, l, r);
		return;	
	}
	if(x <= l && r <= x){
		z[k] = c;
		upd(k, l, r);
		return;
	}
	push(k);
	int mid = (l+r)/2;
	update(k*2, l, mid, x, y, c);
	update(k*2+1, mid+1, r, x, y, c);
	upd(k, l, r);
}
 


int n;
string s[mxn];


unordered_map<string, bool> dict;


bool cross(string a, string b, int &m){
	string ns;
	ns.resize(n);
	
	fr(i, 0, n){
		if(a[i] == b[i]){
			ns[i] = a[i];
		}
		else{
			fr(j, 0, 3){
				if(alp[j] != a[i] && alp[j] != b[i]){
					ns[i] = alp[j];
					break;
				}
			}
		}
	}
	if(!dict[ns]){
		dict[ns] = true;
		s[m++] = ns;
		return true;
	}
	return false;
}

void solve(){
	cin >> n;
	fr(i, 0, 3){
		cin >> s[i];
	}
	int m = 3;
	for(int i = 1; i < m; i ++){
		fr(j, 0, i){
			cross(s[i], s[j], m);
		}
	}
	int q;
	
	string t;
	
	cin >> q;
	cin >> t;
	if(dict[t]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	while(q--){
		int l, r;
		char C;
		cin >> l >> r >> C;
		fr(i, l-1, r) t[i] = C;
		if(dict[t]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
	
}

int main(){
	p[0] = 1;
	fr(i, 1, mxn){
		p[i] = (p[i-1]*A) % B;
	}
	fr(k, 0, 3){
		pre[k][0] = 1;
		fr(i, 1, mxn){
			pre[k][i] = (pre[k][i-1]*A + (int)alp[k])%B;
		}
	}
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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