제출 #1344338

#제출 시각아이디문제언어결과실행 시간메모리
1344338hitsuujCrossing (JOI21_crossing)C++20
26 / 100
7089 ms36292 KiB
#include <bits/stdc++.h>
using namespace std;
#define nama_shortcut nama_aslinya

#define int long long
// 32 slot bit 
// 64 slot bit 
// Memory - Time limit

// integer out of bound

#define pb push_back
#define lc 2*pos
#define rc 2*pos+1
#define pii pair<int,int>
#define fi first
#define se second
//CEK ENDL DAN INT LL
#define endl '\n'
#define inf 1e18
#define ti tuple<int,int,int>
#define quick ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int sf(int a){return (a%mod+mod)%mod;}
int kal(int a,int b){return (sf(a)*sf(b))%mod;}
int tam(int a,int b){return (sf(a)+sf(b))%mod;}
int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;}
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int inv(int a){
    if(a<=1) return 1;
    return mod-(int)(mod/a)*inv(mod%a)%mod;
}
int bag(int a,int b){return kal(sf(a),inv(b));}

void gan(string &a){
    for(auto &c:a){
        if(c=='J') c='1';
        if(c=='O') c='2';
        if(c=='I') c='3';
    }
}
vector<multiset<ti>>isi; 
signed main(){
    quick
    int n;cin>>n;
    string a,b,c;cin>>a>>b>>c;
    a='a'+a;
    b='b'+b;
    c='c'+c;
    gan(a);gan(b);gan(c);
    set<string>sek;
    sek.insert(a);
    sek.insert(b);
    sek.insert(c);
    set<string>inti=sek;
    set<string>udah;
    int masih=1;
    while(sek.size()){
        set<string>baru;
        for(string cur:sek){
            for(string ori:inti){
                string temp=cur;
                for(int i=1;i<=n;i++){
                    int c=cur[i]-'0'; 
                    int cc=ori[i]-'0'; 
                    if(c==cc) continue;
                    int tam=c+cc; 
                    int jadi=6-tam;
                    temp[i]=(char)(jadi+'0');
                }
                if(udah.count(temp)) continue;
                udah.insert(temp);
                baru.insert(temp); 
            }
        }
        swap(baru,sek); 
    }
    for(string sekarang:udah){
        multiset<ti>sekar; 
        for(int l=1;l<=n;l++){
            int r=l;
            while(r+1<=n && sekarang[r+1]==sekarang[r]) r++;
            sekar.insert({l,r,sekarang[l]});
            l=r;
        }
        isi.pb(sekar);
    }

    int q;cin>>q;
    string cur;cin>>cur;
    cur='a'+cur; 
    multiset<ti>kolek;
    for(int l=1;l<=n;l++){
        int r=l;
        while(r+1<=n && cur[r+1]==cur[r]) r++;
        char ch=cur[l];
        if(ch=='J') ch='1';
        if(ch=='O') ch='2';
        if(ch=='I') ch='3';
        kolek.insert({l,r,ch});
        l=r;
    }

    int flag=0;
    // Pake &nw biar gak ngopi multiset yang berat
    for(auto &nw:isi){
        if(kolek==nw) flag=1;
    }
    if(flag) cout<<"Yes";
    else cout<<"No";
    cout<<endl; 
    
    while(q--){
        int l,r;
        char ch;cin>>l>>r>>ch;
        if(ch=='J') ch='1';
        if(ch=='O') ch='2';
        if(ch=='I') ch='3';
        
        while(kolek.size()){
            auto it=kolek.lower_bound({l,0,0});
            if(it!=kolek.begin()){
                it--;
                auto [li,ri,ci]=*it;
                if(ri<l) it++; 
            }
            if(it==kolek.end()) break;
            auto [li,ri,ci]=*it; 
            if(r<li) break; 
            
            kolek.erase(it);
            if(li<l){
                kolek.insert({li,l-1,ci});
            }
            if(r<ri){
                kolek.insert({r+1,ri,ci});
            }
        }
        
        // --- BAGIAN BARU: MERGE TETANGGA ---
        int new_l = l, new_r = r;
        
        // Cek apakah bisa digabung dengan tetangga kanan
        auto it_kanan = kolek.lower_bound({new_l, 0, 0});
        if(it_kanan != kolek.end()){
            auto [li, ri, ci] = *it_kanan;
            if(li == new_r + 1 && ci == ch){
                new_r = ri;
                kolek.erase(it_kanan);
            }
        }
        
        // Cek apakah bisa digabung dengan tetangga kiri
        auto it_kiri = kolek.lower_bound({new_l, 0, 0});
        if(it_kiri != kolek.begin()){
            it_kiri--;
            auto [li, ri, ci] = *it_kiri;
            if(ri == new_l - 1 && ci == ch){
                new_l = li;
                kolek.erase(it_kiri);
            }
        }
        // ------------------------------------
        
        kolek.insert({new_l, new_r, ch});
        
        flag=0;
        // Pake &nw lagi biar optimal waktunya
        for(auto &nw:isi){
            if(kolek==nw) flag=1;
        }
        if(flag) cout<<"Yes";
        else cout<<"No";
        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...