제출 #420065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420065		oolimry	Crossing (JOI21_crossing)	C++17	100 / 100	897 ms	38320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define cnt second
#define hash first
typedef unsigned long long lint;
typedef pair<lint,lint> ii;

const lint prime = 16127;
const lint mod = 1000000007;
lint P[200005];

lint roll[7][200005];
const int dummy = 10;

inline ii merge(ii a, ii b){
	ii res = {b.hash, a.cnt+b.cnt};
	res.hash += a.hash * P[b.cnt];
	res.hash %= mod;
	return res;
}

struct node{
	int s, e, m;
	ii val;
	lint lazy = dummy;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = ii(0, e-s+1);
		if(s != e){
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void apply(int L){
		if(L == dummy) return;
		val = ii(roll[L][e-s+1], e-s+1);
		lazy = L;
	}
	
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = dummy;
	}
	
	void update(int S, int E, int L){
		push();
		if(s == S and E == e) apply(L);
		else{
			if(E <= m) l->update(S,E,L);
			else if(S >= m+1) r->update(S,E,L);
			else l->update(S,m,L), r->update(m+1,E,L);
			val = merge(l->val, r->val);
		}
	}
	
	lint query(){ push(); return val.hash; }
} *root;

int mapto[2000];
lint gethash(string s){
	lint h = 0;
	for(int i = 0;i < sz(s);i++){
		h *= prime;
		h += mapto[(int)s[i]];
		h %= mod;
	}
	return h;
}

string cross(string a, string b){
	string res = "";
	for(int i = 0;i < sz(a);i++){
		if(a[i] == b[i]) res += a[i];
		else{
			res += (char) ((int)('J')+(int)('O')+(int)('I')-a[i]-b[i]);
		}
	}
	return res;
}

set<lint> orihashes;
vector<string> S;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	mapto['J'] = 1;
	mapto['O'] = 3;
	mapto['I'] = 5;
	P[0] = 1;
	for(int i = 1;i <= n;i++) P[i] = (P[i-1] * prime) % mod;
	
	string s1, s2, s3;
	cin >> s1; cin >> s2; cin >> s3;
	S = {s1,s2,s3};
	orihashes.insert(gethash(s1));
	orihashes.insert(gethash(s2));
	orihashes.insert(gethash(s3));
	
	while(true){
		bool found = false;
		int m = sz(S);
		for(int i = 0;i < m;i++){
			for(int j = 0;j < m;j++){
				string s = cross(S[i],S[j]);
				lint h = gethash(s);
				if(orihashes.find(h) == orihashes.end()){
					orihashes.insert(h);
					S.push_back(s);
					found = true;
				}
			}
		}
		if(not found) break;
	}
	
	for(int x = 1;x <= 5;x++){
		lint h = 0;
		for(int i = 1;i <= n;i++){
			h *= prime;
			h += x;
			h %= mod;
			roll[x][i] = h;
		}
	}
	
	int Q; cin >> Q;
	root = new node(1,n);
	string O; cin >> O;
	for(int i = 1;i <= n;i++){
		root->update(i,i,mapto[(int)O[i-1]]);
	}
		
	for(int q = -1;q < Q;q++){
		if(orihashes.find(root->query()) != orihashes.end()) cout << "Yes\n";
		else cout << "No\n";
		
		int l, r; char c; cin >> l >> r >> c;
		root->update(l,r, mapto[(int)c]);
	}
}

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