oj.uz

Submission #861191

# Submission time Handle Problem Language Result Execution time Memory
861191 2023-10-15T15:39:44 Z vjudge1 Crossing (JOI21_crossing) C++17
0 / 100
 506 ms 10288 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 1e6 + 15;
const ll inf = 1e18;
template<class T> bool ckmin(T &a, T b){
	return (a > b ? a=b, true : false);
}
template<class T> bool ckmax(T &a, T b){
	return (a < b ? a=b, true : false);
}
int mul(int a, int b){
	return (a*b)%mod;
}
int add(int a, int b){
	int c = (a+b)%mod;
	if (c<0) c += mod;
	return c;
}
int sub(int a, int b){
	return add(a, -b);
}
int pw(int a, int b){
	int r = 1;
	while (b){
		if (b&1){
			r=mul(a,r);
		}
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}// !!
int inv(int a){
	return pw(a, mod-2);
}
#define ls (idx << 1)
#define rs (idx << 1 | 1)
const int off = (1<<18);
int t[off*2];
int lazy[off*2];
int A[N];
int n;
void push(int idx, int lo, int hi){
	if (!lazy[idx]) return;
	lazy[idx] --;
	int val = lazy[idx];
	t[idx] = mul(add(pw(3ll, hi),1ll), inv(sub(3, 1)));
	t[idx] = sub(t[idx], mul(add(pw(3ll, lo),1ll), inv(sub(3, 1))));
	t[idx] = mul(t[idx], val);
	if (idx < off) {
		lazy[ls] = lazy[idx]+1;
		lazy[rs] = lazy[idx]+1;
	}
	lazy[idx] = 0;
}
void update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
	push(idx,lo,hi);
	if (lo>=r||hi<=l) return;
	if (lo>=l&&hi<=r) {
		lazy[idx]=val+1;
		push(idx, lo, hi);
		return;
	}
	int mi = (lo+hi)/2;
	update(l,r,val,ls,lo,mi);
	update(l,r,val,rs,mi,hi); t[idx] = (t[ls]+t[rs])%mod;
}
void build(int idx){
	if (idx>=off){
		t[idx] = mul(A[idx-off],pw(3ll, idx-off));
		return;
	}
	build(ls);build(rs);
	t[idx] = (t[ls]+t[rs])%mod;
	return;
}
int hsh(string s){
	int p = 1;
	int r = 0;
	for (int i=0;i<n;i++){
		if (s[i]=='J') r = add(r, p*0);
		if (s[i]=='O') r = add(r, p*1);
		if (s[i]=='I') r = add(r, p*2);
		p = mul(p, 3ll);
	}
	return r;
}
string cross(string a, string b){
	string tm;
	tm.resize(n);
	for (int i=0;i<n;i++){
		if (a[i]==b[i]) tm[i] = a[i];
		else {
			if ('J'!=a[i]&&'J'!=b[i]) tm[i] = 'J';
			else if ('O'!=a[i]&&'O'!=b[i]) tm[i] = 'O';
			else if ('I'!=a[i]&&'I'!=b[i]) tm[i] = 'I';
		}
	}
	return tm;
}
set<int> st;
void chk(){
	cout  << (st.find(t[1])!=st.end() ? "Yes" : "No" ) << endl;
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	string a,b,c;
	cin >> a >> b >> c;
	st.insert(hsh(a));
	st.insert(hsh(b));
	st.insert(hsh(c));
	st.insert(hsh(cross(a,b)));
	st.insert(hsh(cross(a,c)));
	st.insert(hsh(cross(b,c)));
	st.insert(hsh(cross(a,cross(b,c))));
	st.insert(hsh(cross(b,cross(a,c))));
	st.insert(hsh(cross(c,cross(a,b))));
	int q;
	cin >> q;
	string tm;
	cin >> tm;
	for (int i=0;i<n;i++){
		if (tm[i]=='J')A[i]=0;
		if (tm[i]=='O')A[i]=1;
		if (tm[i]=='I')A[i]=2;
	}
	build(1);
	chk();
	while (q--){
		int l, r;
		char x;
		cin >> l >> r >> x;
		if (x=='J'){
			update(l-1, r, 0);
		}
		if (x=='O'){
			update(l-1, r, 1);
		}
		if (x=='I'){
			update(l-1, r, 2);
		}
		chk();
	}
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 8268 KB Output is correct
2 Correct 405 ms 7996 KB Output is correct
3 Correct 506 ms 10288 KB Output is correct
4 Correct 278 ms 8020 KB Output is correct
5 Correct 259 ms 8196 KB Output is correct
6 Correct 277 ms 10068 KB Output is correct
7 Correct 280 ms 8292 KB Output is correct
8 Correct 282 ms 10200 KB Output is correct
9 Correct 296 ms 10140 KB Output is correct
10 Incorrect 299 ms 10072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 8268 KB Output is correct
2 Correct 405 ms 7996 KB Output is correct
3 Correct 506 ms 10288 KB Output is correct
4 Correct 278 ms 8020 KB Output is correct
5 Correct 259 ms 8196 KB Output is correct
6 Correct 277 ms 10068 KB Output is correct
7 Correct 280 ms 8292 KB Output is correct
8 Correct 282 ms 10200 KB Output is correct
9 Correct 296 ms 10140 KB Output is correct
10 Incorrect 299 ms 10072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 8268 KB Output is correct
2 Correct 405 ms 7996 KB Output is correct
3 Correct 506 ms 10288 KB Output is correct
4 Correct 278 ms 8020 KB Output is correct
5 Correct 259 ms 8196 KB Output is correct
6 Correct 277 ms 10068 KB Output is correct
7 Correct 280 ms 8292 KB Output is correct
8 Correct 282 ms 10200 KB Output is correct
9 Correct 296 ms 10140 KB Output is correct
10 Incorrect 299 ms 10072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 8268 KB Output is correct
2 Correct 405 ms 7996 KB Output is correct
3 Correct 506 ms 10288 KB Output is correct
4 Correct 278 ms 8020 KB Output is correct
5 Correct 259 ms 8196 KB Output is correct
6 Correct 277 ms 10068 KB Output is correct
7 Correct 280 ms 8292 KB Output is correct
8 Correct 282 ms 10200 KB Output is correct
9 Correct 296 ms 10140 KB Output is correct
10 Incorrect 299 ms 10072 KB Output isn't correct
11 Halted 0 ms 0 KB -