제출 #1127431

#제출 시각아이디문제언어결과실행 시간메모리
1127431vladiliusCrossing (JOI21_crossing)C++20
100 / 100
5088 ms125548 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define arr3 array<int, 3> struct DS{ string a; vector<int> rr; int n, cc; set<pair<pii, char>> st; void init(string as, string b){ a = as; n = (int) a.size(); cc = 0; for (int i = 0; i < n; i++){ st.insert({{i, i}, b[i]}); cc += (b[i] != a[i]); } rr.resize(n); int i = 0; while (i < n){ int j = i; while (j < n && a[i] == a[j]){ j++; } j--; while (i <= j){ rr[i++] = j; } } } bool val(int l, int r, char x){ return (rr[l] >= r && a[l] == x); } void upd(int l, int r, char x){ auto it = st.lower_bound({{l + 1, 0}, 0}); it--; auto [p, y] = (*it); if (p.ff < l){ cc -= !val(p.ff, p.ss, y); st.erase(it); st.insert({{p.ff, l - 1}, y}); st.insert({{l, p.ss}, y}); cc += !val(p.ff, l - 1, y); cc += !val(l, p.ss, y); } it = st.upper_bound({{r + 1, 0}, 0}); it--; p = (*it).ff; y = (*it).ss; if (r < p.ss){ cc -= !val(p.ff, p.ss, y); st.erase(it); st.insert({{p.ff, r}, y}); st.insert({{r + 1, p.ss}, y}); cc += !val(p.ff, r, y); cc += !val(r + 1, p.ss, y); } while (true){ it = st.lower_bound({{l, 0}, 0}); if (it == st.end() || (*it).ff.ff > r) break; auto [p, y] = (*it); cc -= !val(p.ff, p.ss, y); st.erase(it); } st.insert({{l, r}, x}); cc += !val(l, r, x); } bool get(){ return !cc; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; string a, b, c; cin>>a>>b>>c; vector<char> C = {'J', 'O', 'I'}; auto f = [&](string x, string y){ string t; for (int i = 0; i < n; i++){ if (x[i] == y[i]){ t += x[i]; continue; } for (char s: C){ if (s != x[i] && s != y[i]){ t += s; break; } } } return t; }; vector<string> all = {a, b, c, f(a, b), f(b, c), f(a, c), f(f(a, b), c), f(f(b, c), a), f(f(a, c), b)}; int q; cin>>q; string t; cin>>t; DS T[9]; for (int i = 0; i < 9; i++){ T[i].init(all[i], t); } auto check = [&](string s){ for (int i = 0; i < 9; i++){ if (T[i].get()){ cout<<"Yes"<<"\n"; return; } } cout<<"No"<<"\n"; return; }; check(t); while (q--){ int l, r; char S; cin>>l>>r>>S; l--; r--; for (int i = 0; i < 9; i++){ T[i].upd(l, r, S); } check(t); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...