제출 #1344996

#제출 시각아이디문제언어결과실행 시간메모리
1344996hitsuujCrossing (JOI21_crossing)C++20
0 / 100
130 ms1000 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,char>
#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='a'+b;
    c='a'+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); 
    }

    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 c=cur[l];
        if(c=='J') c='1';
        if(c=='O') c='2';
        if(c=='I') c='3';
        cur[l]=c;
        kolek.insert({l,r,c});
        l=r;
    }
    int flag=0;
    for(auto x:udah){
        if(cur==x) flag=1; 
    }
    
    if(flag) cout<<"Yes";
    else cout<<"No";
    cout<<endl;
     
    while(q--){
        int l,r;
        char c;cin>>l>>r>>c;
        if(c=='J') c='1';
        if(c=='O') c='2';
        if(c=='I') c='3';
        int tt=10;
        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){
                int rr=ri; 
                rr=min(rr,l-1);
                kolek.insert({li,rr,ci});
            }
            if(r<ri){
                int ll=li;
                ll=max(ll,r+1);
                kolek.insert({ll,ri,ci});
            }
        }
        kolek.insert({l,r,c});
        int flag=0;
        string mami="a";
        for(auto [li,ri,ci]:kolek){
            for(int i=li;i<=ri;i++){
                mami+=ci;
            }
        }
        for(auto x:udah){
            if(mami==x) flag=1; 
        }
        if(flag) cout<<"Yes";
        else cout<<"No";
        cout<<endl; 
    }
}
// kita coba aja simpen trus cari semacam trienya gitu 
// simpen mulai dari mana akhir mana dan jenisnya 


// aaaaaaa
//  bbbb 


// aaaa
//  bbbbb 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...