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 <iostream>
#define NMAX 200000
using namespace std;
//ifstream cin(".in");
//ofstream cout(".out");
string s[10], t;
void add2Strings(int a, int b, int sum, int n) {
s[sum].resize(n + 1, 0);
s[sum][0] = ' ';
for(int i = 1; i <= n; i++) {
if(s[a][i] == s[b][i]) {
s[sum][i] = s[a][i];
} else {
if('J' != s[a][i] && 'J' != s[b][i])
s[sum][i] = 'J';
if('O' != s[a][i] && 'O' != s[b][i])
s[sum][i] = 'O';
if('I' != s[a][i] && 'I' != s[b][i])
s[sum][i] = 'I';
}
}
}
void buildAllPosStrings(int n) {
add2Strings(1, 2, 4, n);
add2Strings(2, 3, 5, n);
add2Strings(3, 1, 6, n);
add2Strings(4, 3, 7, n);
add2Strings(5, 1, 8, n);
add2Strings(6, 2, 9, n);
}
struct node{
bool equal;
char lazy, specialProp;
}arboriAint[10][NMAX * 4];
void buildArb(int indexS, int p, int lInt, int rInt) {
if(lInt == rInt) {
if(s[indexS][lInt] == t[lInt]) {
arboriAint[indexS][p].equal = 1;
}
arboriAint[indexS][p].specialProp = s[indexS][lInt];
return;
}
int med = (lInt + rInt) / 2;
buildArb(indexS, p * 2, lInt, med);
buildArb(indexS, p * 2 + 1, med + 1, rInt);
if(arboriAint[indexS][p * 2].equal == arboriAint[indexS][p * 2 + 1].equal && arboriAint[indexS][p * 2].equal == 1)
arboriAint[indexS][p].equal = 1;
if(arboriAint[indexS][p * 2].specialProp == arboriAint[indexS][p * 2 + 1].specialProp)
arboriAint[indexS][p].specialProp = arboriAint[indexS][p * 2].specialProp;
}
void propagate(node aint[], int p) {
if(aint[p].lazy == 0)
return;
aint[p * 2].lazy = aint[p].lazy;
aint[p * 2 + 1].lazy = aint[p].lazy;
aint[p * 2].equal = ((aint[p * 2].specialProp == aint[p].lazy) && (aint[p].lazy != 0));
aint[p * 2 + 1].equal = ((aint[p * 2 + 1].specialProp == aint[p].lazy && (aint[p].lazy != 0)));
aint[p].lazy = 0;
}
void update(node aint[], int p, int lInt, int rInt, int lTarget, int rTarget, char modValue) {
if(lInt == rInt) {
aint[p].equal = (modValue == aint[p].specialProp);
return;
}
propagate(aint, p);
if(lTarget <= lInt && rInt <= rTarget) {
aint[p].equal = (modValue == aint[p].specialProp);
aint[p].lazy = modValue;
return;
}
int med = (lInt + rInt) / 2;
if(lTarget <= med) {
update(aint, p * 2, lInt, med, lTarget, rTarget, modValue);
}
if(med + 1 <= rTarget) {
update(aint, p * 2 + 1, med + 1, rInt, lTarget, rTarget, modValue);
}
aint[p].equal = ((aint[p * 2].equal == aint[p * 2 + 1].equal) && aint[p * 2].equal == 1);
}
bool isEqual(node aint[]) {
return aint[1].equal;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q, l, r, i;
char ch;
bool match;
cin>>n;
cin>>s[1];
s[1] = " " + s[1];
cin>>s[2];
s[2] = " " + s[2];
cin>>s[3];
s[3] = " " + s[3];
buildAllPosStrings(n);
cin>>q;
cin>>t;
t = " " + t;
for(i = 1; i <= 9; i++) {
buildArb(i, 1, 1, n);
}
match = 0;
for(i = 1; i <= 9; i++) {
if(isEqual(arboriAint[i]) == 1) {
match = 1;
}
}
if(match) {
cout<<"YES\n";
} else {
cout<<"NO\n";
}
while(q--) {
cin>>l>>r>>ch;
for(i = 1; i <= 9; i++) {
update(arboriAint[i], 1, 1, n, l, r, ch);
}
match = 0;
for(i = 1; i <= 9; i++) {
if(isEqual(arboriAint[i]) == 1) {
match = 1;
}
}
if(match) {
cout<<"YES\n";
} else {
cout<<"NO\n";
}
}
return 0;
}
# | 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... |