This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18;
vector<string> get_strings(string &xx, string &y, string &z){
string s[3] = {xx, y, z};
int n = int(s[0].length());
map<string, int> mp;
queue<string> q;
for(int l = 0; l < 3; ++l) mp[s[l]] = 1, q.emplace(s[l]);
char t[3] = {'J', 'O', 'I'};
//~ int cnt = 0;
vector<string> ret;
while(!q.empty()){
string x = q.front(); q.pop();
string tt = ""; tt.resize(n);
for(int l = 0; l < 3; ++l){
for(int i = 0; i < n; ++i) if(x[i] == s[l][i]) tt[i] = x[i];
else{
int a, b;
for(int j = 0; j < 3; ++j) if(t[j] == x[i]) a = j;
for(int j = 0; j < 3; ++j) if(t[j] == s[l][i]) b = j;
if(a && b) tt[i] = t[0];
else if(max(a, b) > 1) tt[i] = t[1];
else tt[i] = t[2];
}
if(mp[tt] != 1) mp[tt] = 1, q.emplace(tt); //, cout << ":\n" << x << "\n" << s[l] << "\n" << tt << "\n\n";
}
//~ cout << x << "\n";
ret.emplace_back(x);
}
return ret;
}
ll mod = 998244353ll;
int base = 1;
struct seg{
vector<ll> t, p, tmp, powp;
void build(int i, int s, int e){
for(int j = s; j <= e; ++j) tmp[i] += powp[j];
int mid = (s+e)>>1;
if(s != e) build(i<<1, s, mid), build(i<<1|1, mid+1, e);
}
void init(int n){
while(base < n) base <<= 1;
t.resize(base<<1, 0), tmp.resize(base<<1, 0), powp.resize(base+1), p.resize(base<<1, 0);
powp[0] = 1;
for(int i = 1; i <= base; ++i) powp[i] = powp[i-1]*998244353ll;
build(1, 1, base);
}
void add(int i, ll pr){ t[i] = tmp[i]*pr, p[i] = pr; }
void push(int i){ if(p[i]) add(i<<1, p[i]), add(i<<1|1, p[i]), p[i] = 0; }
void update(int i, int s, int e, int x, int y, ll pr){
if(x <= s && e <= y) return void(add(i, pr));
int mid = (s+e)>>1; push(i);
if(x <= mid) update(i<<1, s, mid, x, y, pr);
if(mid < y) update(i<<1|1, mid+1, e, x, y, pr);
t[i] = t[i<<1]+t[i<<1|1];
}
};
void answer(){
int n, q; scanf("%d", &n);
string s[3] = {"", "", ""}, t="";
char c;
for(int l = 0; l < 3; ++l){
c = getchar_unlocked();
for(int i = 0; i < n; ++i) c = getchar_unlocked(), s[l] += c;
}
scanf("%d\n", &q);
for(int i = 0; i < n; ++i) c = getchar_unlocked(), t += c;
vector<string> st = get_strings(s[0], s[1], s[2]);
vector<ll> powp(n+1); powp[0] = 1;
for(int i = 1; i <= n; ++i) powp[i] = powp[i-1]*998244353ll;
unordered_map<ll, bool> mp;
for(string &u : st){
ll hash = 0;
for(int i = 0; i < n; ++i) hash += ll(u[i])*powp[i+1];
mp[hash] = 1;
//~ printf("%lld\n", hash);
}
seg seg; seg.init(n+1);
for(int i = 0; i < n; ++i) seg.t[i+base] = ll(t[i])*powp[i+1];
for(int i = base-1; i; --i) seg.t[i] = seg.t[i<<1]+seg.t[i<<1|1];
printf(mp[seg.t[1]] ? "Yes\n" : "No\n");
//~ printf("%lld\n", seg.t[1]);
for(++q; --q; ){
int a, b;
scanf("%d%d %c", &a, &b, &c);
seg.update(1, 1, base, a, b, ll(c));
printf(mp[seg.t[1]] ? "Yes\n" : "No\n");
//~ printf("%lld\n", seg.t[1]);
}
}
int main(){
int T = 1;
//~ ios_base::sync_with_stdio(0); cin.tie(0);
for(++T; --T; ) answer();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void answer()':
Main.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | int n, q; scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d\n", &q);
| ~~~~~^~~~~~~~~~~~
Main.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d%d %c", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |