# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
697474 | 2023-02-10T02:44:25 Z | Sandarach151 | Crossing (JOI21_crossing) | C++17 | 0 ms | 0 KB |
#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; }