Submission #1304812

#TimeUsernameProblemLanguageResultExecution timeMemory
1304812baktrrCrossing (JOI21_crossing)C++20
26 / 100
7089 ms5568 KiB
/**
  III     U   U  N   N  DDDD   EEEEE  RRRR   SSSS  TTTTT  AAAAA  N   N  DDDD      I  TTTTT     N   N   OOO   W   W
   I      U   U  NN  N  D   D  E      R   R  S       T    A   A  NN  N  D   D     I    T       NN  N  O   O  W   W
   I      U   U  N N N  D   D  EEEE   RRRR   SSSS    T    AAAAA  N N N  D   D     I    T       N N N  O   O  W W W
   I      U   U  N  NN  D   D  E      R  R      S    T    A   A  N  NN  D   D     I    T       N  NN  O   O  WW WW
  III     UUUUU  N   N  DDDD   EEEEE  R   R  SSSS    T    A   A  N   N  DDDD      I    T       N   N   OOO   W   W
**/

//18.09.25
#include <bits/stdc++.h>

// #pragma optimize("g", on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroint-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define F first
#define ent '\n'
#define S second
#define no "NO\n"
#define in insert
#define yes "YES\n"
#define pp pop_back
#define pb push_back
#define int long long
#define sz(w) w.size()
#define pii pair <int, int>
#define all(w) w.begin(), w.end()
#define rall(w) w.rbegin(), w.rend()
#define Yeah ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MOD = 998244353, M = 4e5 + 7, N = 2e5 + 7, INF = 1e18, inf = 1e9 + 7, LOG = 20 , mod = 1e9 + 7 ;

// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

char t[4 * N] , lazy[4 * N] ;
string s ;
int n ;

void push(int v , int tl , int tr) {
    if(lazy[v] == 0) return ;
    t[v + v] = lazy[v] ;
    t[v + v + 1] = lazy[v] ;
    lazy[v + v] = lazy[v] ;
    lazy[v + v + 1] = lazy[v] ;
    lazy[v] = 0 ;
}

void build(int v , int tl , int tr) {
    if(tl == tr) {
        t[v] = s[tl] ;
        return;
    }
    int mid = (tl + tr) / 2 ;
    build(v + v , tl , mid) ;
    build(v + v + 1 , mid + 1 , tr) ;
}

void upd(int v , int tl , int tr , int l , int r , char c) {
    if(l > r) return ;
    if(tl == l && tr == r) {
        t[v] = c ;
        lazy[v] = c ; 
        return ;
    }
    push(v , tl , tr) ;
    int mid = (tl + tr) / 2 ;
    upd(v + v , tl , mid , l , min(r , mid) , c) ;
    upd(v + v + 1 , mid + 1 , tr , max(l , mid + 1) , r , c) ;
}

void get(int v , int tl , int tr , string &res) {
    if(tl == tr) {
        res += t[v] ;
        return ;
    }
    push(v , tl , tr) ;
    int mid = (tl + tr) / 2 ;
    get(v + v , tl , mid , res) ;
    get(v + v + 1 , mid + 1 , tr , res) ;
}

void accepted() {
    cin >> n ;
    string a , b , c ;
    cin >> a >> b >> c ;
    vector <string> ans ;
    ans.pb(a) , ans.pb(b) , ans.pb(c) ;
    string res , res1 , res2 ;
    string mat = "IJO" ; 
    for(int i = 0 ; i < n ; i++) {
        if(a[i] == b[i]) {
            res += a[i] ;
        }
        else {
            string h ;
            h += a[i] ;
            h += b[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                res += "I" ;
            }
            else if(mat[1] != h[1]) {
                res += "J" ;
            }
            else {
                res += "O" ;
            }
        }
    }
    ans.pb(res) ;
    res1 = res ;
    res = "" ; 
    for(int i = 0 ; i < n ; i++) {
        if(a[i] == c[i]) {
            res += a[i] ;
        }
        else {
            string h ;
            h += a[i] ;
            h += c[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                res += "I" ;
            }
            else if(mat[1] != h[1]) {
                res += "J" ;
            }
            else {
                res += "O" ;
            }
        }
    }
    ans.pb(res) ;
    res2 = res ;
    res = "" ;
    for(int i = 0 ; i < n ; i++) {
        if(b[i] == c[i]) {
            res += b[i] ;
        }
        else {
            string h ;
            h += b[i] ;
            h += c[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                res += "I" ;
            }
            else if(mat[1] != h[1]) {
                res += "J" ;
            }
            else {
                res += "O" ;
            }
        }
    }
    ans.pb(res) ;
    string ser ;
    for(int i = 0 ; i < n ; i++) {
        if(res1[i] == res2[i]) {
            ser += res1[i] ;
        }
        else {
            string h ;
            h += res1[i] ;
            h += res2[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                ser += "I" ;
            }
            else if(mat[1] != h[1]) {
                ser += "J" ;
            }
            else {
                ser += "O" ;
            }
        }
    }
    ans.pb(ser) ;
    ser = "" ;
    for(int i = 0 ; i < n ; i++) {
        if(res1[i] == res[i]) {
            ser += res[i] ;
        }
        else {
            string h ;
            h += res1[i] ;
            h += res[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                ser += "I" ;
            }
            else if(mat[1] != h[1]) {
                ser += "J" ;
            }
            else {
                ser += "O" ;
            }
        }
    }
    ans.pb(ser) ;
    ser = "" ;
    for(int i = 0 ; i < n ; i++) {
        if(res2[i] == res[i]) {
            ser += res[i] ;
        }
        else {
            string h ;
            h += res2[i] ;
            h += res[i] ;
            sort(all(h)) ;
            if(mat[0] != h[0]) {
                ser += "I" ;
            }
            else if(mat[1] != h[1]) {
                ser += "J" ;
            }
            else {
                ser += "O" ;
            }
        }
    }
    ans.pb(ser) ;
    int q ;
    cin >> q ;
    cin >> s ;
    build(1 , 0 , n - 1) ;
    bool ok = 0 ;
    string st ;
    get(1 , 0 , n - 1 , st) ;
    for(auto sta : ans) {
        if(sta == st) {
            ok = 1 ;
            break;
        }
    }
    if(ok) {
        cout << "Yes" << ent ;
    }
    else {
        cout << "No" << ent ;
    }
    while(q -- ) {
        int l , r ;
        char ch ;
        cin >> l >> r >> ch ;
        l-- , r-- ;
        upd(1 , 0 , n - 1 , l , r , ch) ;
        bool ok = 0 ;
        string st ;
        get(1 , 0 , n - 1 , st) ;
        for(auto sta : ans) {
            if(sta == st) {
                ok = 1 ;
                break;
            }
        }
        if(ok) {
            cout << "Yes" << ent ;
        }
        else {
            cout << "No" << ent ;
        }
    }
}

// I first 
// J second
// O third


signed main() {
    Yeah
 
    // PLS NeverGiveUp

    // freopen("cowpatibility.in", "r", stdin) ;  
    // freopen("cowpatibility.out", "w", stdout) ;

    int T = 1 ;
    // cin >> T ;
    while(T--) {
        accepted();
        cout << endl ;
    }
}

/**

**/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...