# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
697474 | Sandarach151 | Crossing (JOI21_crossing) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
string cur, targ;
struct node{
node *l, *r;
int start, mid, end;
char curequals, targequals;
bool equals;
node(int _start, int _end, string _cur, string _targ): start(_start), mid((_start+_end)/2), end(_end), cur(_cur), targ(_targ){
if(start!=end){
l = new node(start, mid, cur, targ);
r = new node(mid+1, end, cur, targ);
if(l->targequals==r->targequals){
this->targequals=l->targequals;
}
else{
this->targequals='0';
}
if(l->curequals==r->curequals){
this->curequals=l->curequals;
}
else{
this->curequals='0';
}
this->equals=(l->equals && r->equals);
}
else{
this->targequals = targ[start];
this->curequals = cur[start];
this->equals = (this->targequals==this->curequals);
}
}
void update(char c, int left, int right){
if(start==left && end==right){
this->curequals = c;
this->equals = (this->targequals!='0' && this->curequals==this->targequals);
}
else{
if(this->curequals!='0'){
l->curequals = this->curequals;
l->equals = (l->targequals==l->curequals);
r->curequals = this->curequals;
r->equals = (r->targequals==r->curequals);
this->curequals = '0';
}
if(left>mid){
r->update(c, left, right);
}
else if(right<=mid){
l->update(c, left, right);
}
else{
l->update(c, left, mid);
r->update(c, mid+1, right);
}
this->equals = (r->equals && l->equals);
}
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
int q;
cin >> q;
string init;
cin >> init;
cur = init;
targ = a;
node root(0, n-1, init, a);
if(root.equals){
cout << "Yes\n";
}
else{
cout << "No\n";
}
for(int i=0; i<q; i++){
int d, e;
char f;
cin >> d >> e >> f;
d--;
e--;
root.update(f, d, e);
if(root.equals){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
return 0;
}