제출 #1345182

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

#define int long long
#define pb push_back
#define lc 2*pos
#define rc 2*pos+1
#define pii pair<int,int>
#define fi first
#define se second
#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);

void gan(string &a){
    for(auto &c:a){
        if(c=='J') c='1';
        if(c=='O') c='2';
        if(c=='I') c='3';
    }
}

string targets[15];
int pref[15][4][200005]; 
int num_targets = 0;

int st[4 * 200005]; 
int lz[4 * 200005]; 

int get_mask(int l, int r, int val) {
    int mask = 0;
    int len = r - l + 1;
    for (int k = 0; k < num_targets; k++) {
        if (pref[k][val][r] - pref[k][val][l - 1] == len) {
            mask |= (1 << k); 
        }
    }
    return mask;
}

void build(int pos, int l, int r, const string& cur) {
    lz[pos] = 0;
    if (l == r) {
        int val = cur[l] - '0';
        int mask = 0;
        for(int k = 0; k < num_targets; k++){
            if (targets[k][l] - '0' == val) {
                mask |= (1 << k);
            }
        }
        st[pos] = mask;
        return;
    }
    int mid = (l + r) / 2;
    build(lc, l, mid, cur);
    build(rc, mid + 1, r, cur);
    st[pos] = st[lc] & st[rc]; 
}

void push(int pos, int l, int r) {
    if (lz[pos] != 0) {
        int mid = (l + r) / 2;
        int val = lz[pos];

        lz[lc] = val;
        st[lc] = get_mask(l, mid, val); 

        lz[rc] = val;
        st[rc] = get_mask(mid + 1, r, val); 

        lz[pos] = 0; 
    }
}

void update(int pos, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        lz[pos] = val;
        st[pos] = get_mask(l, r, val); 
        return;
    }
    push(pos, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(lc, l, mid, ql, qr, val);
    if (qr > mid) update(rc, mid + 1, r, ql, qr, val);
    st[pos] = st[lc] & st[rc];
}

signed main(){
    quick
    int n;cin>>n;
    
    string a,b,c;cin>>a>>b>>c;
    // INI DIA FIX SAKTI LU
    a='a'+a; b='a'+b; c='a'+c; 
    gan(a);gan(b);gan(c);
    
    set<string>sek = {a, b, c};
    set<string>inti = sek;
    set<string>udah;
    
    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 ci=cur[i]-'0'; 
                    int cci=ori[i]-'0'; 
                    if(ci==cci) continue;
                    temp[i]=(char)((6-(ci+cci))+'0');
                }
                if(udah.count(temp)) continue;
                udah.insert(temp);
                baru.insert(temp); 
            }
        }
        swap(baru,sek); 
    }
    
    for(string s : udah){
        targets[num_targets] = s;
        for(int i=1; i<=n; i++){
            for(int k=1; k<=3; k++){
                pref[num_targets][k][i] = pref[num_targets][k][i-1];
            }
            pref[num_targets][s[i]-'0'][i]++; 
        }
        num_targets++;
    }

    int q;cin>>q;
    string cur;cin>>cur;
    cur='a'+cur; 
    gan(cur);
    
    build(1, 1, n, cur);

    if (st[1] > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    while(q--){
        int l, r;
        char ch; cin >> l >> r >> ch;
        int val = (ch == 'J' ? 1 : (ch == 'O' ? 2 : 3));
        
        update(1, 1, n, l, r, val);
        
        if (st[1] > 0) cout << "Yes" << endl;
        else cout << "No" << 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...