#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
// #ifndef ONLINE_JUDGE
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
// #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
struct SEG{
vector<int> s, t; int n;
vector<int> exp, laz;
vector<bool> seg;
SEG(){}
SEG(vector<int> s, vector<int> t): s(s), t(t){
n = sz(s);
exp.resize(n<<2), seg.resize(n<<2);
laz.assign(n<<2, -1);
build(1, 0, n);
}
void build(int x, int lx, int rx){
if(lx + 1 == rx){
exp[x] = s[lx], seg[x] = s[lx] == t[lx];
return;
}
int mid = (lx + rx)>>1;
build(x<<1, lx, mid), build(x<<1|1, mid, rx);
seg[x] = seg[x<<1]&seg[x<<1|1];
if(exp[x<<1] == -1 || exp[x<<1|1] == -1 || exp[x<<1] - exp[x<<1|1]) exp[x] = -1;
else exp[x] = exp[x<<1];
}
void updNode(int x, int k){
seg[x] = exp[x] == k;
laz[x] = k;
}
void shift(int x){
if(laz[x] + 1){
updNode(x<<1, laz[x]), updNode(x<<1|1, laz[x]);
laz[x] = -1;
}
}
void upd(int l, int r, int k, int x, int lx, int rx){
if(l <= lx && r >= rx){
updNode(x, k);
return;
}
shift(x);
int mid = (lx + rx)>>1;
if(l < mid) upd(l, r, k, x<<1, lx, mid);
if(mid < r) upd(l, r, k, x<<1|1, mid, rx);
seg[x] = seg[x<<1]&seg[x<<1|1];
}
void upd(int l, int r, int k){ upd(l, r, k, 1, 0, n); }
bool get(){
return seg[1];
}
vector<int> gt, tg;
void dfs(int x, int lx, int rx){
if(lx + 1 == rx) {
gt.pb(laz[x]), tg.pb(exp[x]);
return;
}
shift(x);
int mid = (lx + rx)>>1;
dfs(x<<1, lx, mid), dfs(x<<1|1, mid, rx);
}
void dfs(){
gt.clear(), tg.clear();
dfs(1, 0, n);
}
};
vector<int> comb(vector<int> a, vector<int> b){
vector<int> res = a;
rep(i,0,sz(a)) res[i] = (6 - a[i] - b[i])%3;
return res;
}
int ID(char c){
if(c == 'J') return 0;
if(c == 'O') return 1;
return 2;
}
string inv(vector<int> t){
string res;
for(int c: t){
if(c == 0) res.pb('J');
if(c == 1) res.pb('O');
if(c == 2) res.pb('I');
}
return res;
}
int main(){ IOS();
int n; cin >> n;
vector<int> s[4];
rep(i,0,3){
string t; cin >> t;
for(char c: t) s[i].pb(ID(c));
}
int q; cin >> q;
vector<int> t;
string tmp; cin >> tmp;
for(char c: tmp) t.pb(ID(c));
set<vector<int>> st;
vector<SEG> sg;
vector<vector<int>> dq;
rep(i,0,3) st.insert(s[i]), dq.pb(s[i]), sg.pb(SEG(s[i], t));
while(sz(dq)){
vector<int> r = dq.back(); dq.pop_back();
rep(i,0,3){
vector<int> x = comb(r, s[i]);
if(st.find(x) == end(st)) st.insert(x), dq.pb(x), sg.pb(SEG(x, t));
}
}
bool ans = false;
rep(i,0,sz(sg)) ans |= sg[i].get();
cout << (ans? "YES\n": "NO\n");
while(q--){
int l, r; char c; cin >> l >> r >> c; l--;
int id = ID(c);
bool ans = false;
rep(i,0,sz(sg)) sg[i].upd(l, r, id), ans |= sg[i].get();
cout << (ans? "YES\n": "NO\n");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
