Submission #1159225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159225		brinton	Crossing (JOI21_crossing)	C++20	100 / 100	318 ms	30812 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD ((1LL << 61)-1)
const int B = 9973;//! change to 9973
string cross(string a,string b){
    int L = a.size();
    string ret(L,'.');
    for(int i = 0;i < L;i++){
        if(a[i] == b[i]){
            ret[i] = a[i];
            continue;
        }
        int J = false,O = false,I = false;
        if(a[i] == 'J' || b[i] == 'J')J = true;
        if(a[i] == 'O' || b[i] == 'O')O = true;
        if(a[i] == 'I' || b[i] == 'I')I = true;
        if(!J) ret[i] = 'J';
        if(!O) ret[i] = 'O';
        if(!I) ret[i] = 'I';
    }
    return ret;
}

vector<int> powp;
int pow(int l,int r){
    if(l == 0){
        return powp[r];
    }else{
        return (powp[r]-powp[l-1]+MOD)%MOD;
    }
}
// J:0, O:1, I:2
int Hash(string s){
    int ret = 0;
    for(int i = 0;i < s.size();i++){
        int cur = 0;
        if(s[i] == 'O')cur = 1;
        if(s[i] == 'I')cur = 2;
        
        ret += cur*pow(i,i);
        ret %= MOD;
    }
    return ret;
}
struct SEG{
    private:
    vector<int> tree;
    vector<int> lazy;
    int N;
    int H;// J:0,O:1,I:2
    void push(int idx,int l,int r){
        if(lazy[idx] == -1)return;
        if(l == r){
            lazy[idx] == -1;
            return;
        }
        int m = (l+r)/2;
        tree[idx*2] = lazy[idx]*H*pow(l,m);
        tree[idx*2+1] = lazy[idx]*H*pow(m+1,r);
        lazy[idx*2] = lazy[idx*2+1] = lazy[idx];
        lazy[idx] = -1;
    }
    void modify(int l,int r,int idx,int L,int R,int type){
        // push lazy
        push(idx,l,r);
        if(L == l && r == R){
            tree[idx] = type*H*pow(l,r);
            lazy[idx] = type;
            return;
        }
        int m = (l+r)/2;
        if(R <= m){
            modify(l,m,idx*2,L,R,type);
        }else if(L >= m+1){
            modify(m+1,r,idx*2+1,L,R,type);
        }else{
            modify(l,m,idx*2,L,m,type);
            modify(m+1,r,idx*2+1,m+1,R,type);
        }
        tree[idx] = (tree[idx*2]+tree[idx*2+1])%MOD;
    }
    public:
    SEG(int iN,int iH){
        N = iN;
        H = iH;
        tree = vector<int>(4*N+5,0);
        lazy = vector<int>(4*N+5,0);
    }
    void set(int l,int r){
        modify(0,N-1,1,l,r,1);
    }
    void clear(int l,int r){
        modify(0,N-1,1,l,r,0);
    }
    int get(){
        return tree[1];// range all
    }
};
signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N;cin >> N;
    // === init powp ===
    powp.resize(N+1);
    powp[0] = 1;
    for(int i = 1;i <= N;i++){
        powp[i] = (__int128_t)powp[i-1]*B%MOD;
    }
    for(int i = 1;i <= N;i++){
        powp[i] += powp[i-1];
        powp[i] %= MOD;
    }
    //! debug
    // for(auto i:powp)cout << i << " ";cout << endl;
    // === input string, crossing, hashing === 
    string a,b,c,ab,ac,bc,abc1,abc2,abc3;
    cin >> a >> b >> c;
    ab = cross(a,b),ac = cross(a,c),bc = cross(b,c);
    abc1 = cross(a,bc),abc2 = cross(ab,c),abc3 = cross(ac,b);
    int ha = Hash(a),hb = Hash(b),hc = Hash(c),hab = Hash(ab),hac = Hash(ac),hbc = Hash(bc);
    int habc1 = Hash(abc1),habc2 = Hash(abc2), habc3 = Hash(abc3);


    // === Queries
    int Q;cin >> Q;
    auto chk = [&](int ht){
        return (ht == ha || ht == hb || ht == hc) || (ht == hab || ht == hac || ht == hbc) || 
                (ht == habc1 || ht == habc2 || ht == habc3);
    };
    string T;cin >> T;
    // J:0, O:1, I:2
    SEG O(N,1);// 1
    SEG I(N,2);// 2
    for(int i = 0;i < N;i++){
        if(T[i] == 'O'){
            O.set(i,i);
        }
        if(T[i] == 'I'){
            I.set(i,i);
        }
    }

    cout << (chk((O.get()+I.get())%MOD)?"Yes\n":"No\n");
    while(Q--){
        int l,r;char c;
        cin >> l >> r >> c;
        l--;r--;
        if(c == 'J'){
            O.clear(l,r);
            I.clear(l,r);
        }else if(c == 'O'){
            O.set(l,r);
            I.clear(l,r);
        }else if(c == 'I'){
            O.clear(l,r);
            I.set(l,r);
        }
        // cout << T << endl;
        cout << (chk((O.get()+I.get())%MOD)?"Yes\n":"No\n");

    }

}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51