Submission #537742

#	Time	Username	Problem	Language	Result	Execution time	Memory
537742		Mahfel	Crossing (JOI21_crossing)	C++17	100 / 100	359 ms	25996 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
const ll MXN = 2e5 + 20 , PR1 = 19 , PR2 = 31 , MOD1 = 998244353 , MOD2 = 1e9 + 9;
ll po1[MXN] , po2[MXN] , pref1[MXN] , pref2[MXN];
set<pair<ll,ll>> H;
pair<ll,ll> Hash(vector<int> v) {
    ll h1 = 0 , h2 = 0 , p1 = 1 , p2 = 1;
    for(auto x : v) {
        x++;
        h1 += x*p1 % MOD1; h1 %= MOD1;
        h2 += x*p2 % MOD2; h2 %= MOD2;
        p1 *= PR1; p1 %= MOD1;
        p2 *= PR2; p2 %= MOD2;
    }
    return {h1 , h2};
}
vector<int> str[3];
int n,q;
void prep(int c1 , int c2 , int c3) {
    vector<int> res(n);
    for(int i = 0 ; i < n ; i++) {
        res[i] = ((c1*str[0][i]) + (c2*str[1][i]) + (c3*str[2][i])) % 3;
    }
    H.insert(Hash(res));
}
inline ll P(ll a , ll b , ll MOD) {
    ll res = 1;
    while(b > 0) {
        if(b&1) {
            res *= a; res %= MOD;
        }
        a *= a; a %= MOD;
        b >>= 1;
    }
    return res;
}

struct seg_tree {
    int size;
    vector<pair<ll,ll>> hsh;
    vector<int> layZ;
    seg_tree() {
        size = 0;
    }
    void init() {
        size = 1;
        while(size < n) size <<= 1;
        hsh.assign(2*size , {0 , 0});
        layZ.assign(2*size , -1);
    }
    void build(int x , int lx , int rx , vector<int> &v) {
        if(rx-lx == 1) {
            if(lx < n) {
                hsh[x] = {v[lx]+1 , v[lx]+1};
            }
            return;
        }
        int m = (lx+rx)/2;
        build(lt(x) , lx , m , v);
        build(rt(x) , m , rx , v);
        pair<ll,ll> p = hsh[lt(x)] , q = hsh[rt(x)];
        hsh[x].first = (p.first + q.first*po1[m-lx]%MOD1) % MOD1;
        hsh[x].second = (p.second + q.second*po2[m-lx]%MOD2) % MOD2;
    }
    void build(vector<int> &v) {
        build(0 , 0 , size , v);
    }

    void shift(int x , int lx , int rx) {
        if(rx-lx == 1 || layZ[x] == -1) return;
        layZ[lt(x)] = layZ[x];
        layZ[rt(x)] = layZ[x];
    }
    void update(int x , int lx , int rx) {
        if(layZ[x] == -1) return;
        layZ[x]++;
        hsh[x].first = layZ[x] * pref1[rx-lx-1] % MOD1;
        hsh[x].second = layZ[x] * pref2[rx-lx-1] % MOD2;
        layZ[x] = -1;
    }

    void set(int x , int lx , int rx , int l , int r , int k) {
        if(lx >= l && rx <= r) {
            layZ[x] = k;
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        set(lt(x) , lx , m , l , r , k);
        set(rt(x) , m , rx , l , r , k);

        pair<ll,ll> p = hsh[lt(x)] , q = hsh[rt(x)];
        hsh[x].first = (p.first + q.first*po1[m-lx]%MOD1) % MOD1;
        hsh[x].second = (p.second + q.second*po2[m-lx]%MOD2) % MOD2;
        layZ[x] = -1;
    }
    void set(int l , int r , int k) {
        set(0 , 0 , size , l , r , k);
    }

    pair<ll,ll> get(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return hsh[x];
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return {0 , 0};
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        pair<ll,ll> p = get(lt(x) , lx , m , l , r);
        pair<ll,ll> q = get(rt(x) , m , rx , l , r);
        pair<ll,ll> res;
        res.first = (p.first + q.first*po1[m-lx]%MOD1) % MOD1;
        res.second = (p.second + q.second*po2[m-lx]%MOD2) % MOD2;
        
        p = hsh[lt(x)] , q = hsh[rt(x)];
        hsh[x].first = (p.first + q.first*po1[m-lx]%MOD1) % MOD1;
        hsh[x].second = (p.second + q.second*po2[m-lx]%MOD2) % MOD2;
        layZ[x] = -1;

        return res;
    }
    pair<ll,ll> get(int l , int r) {
        return get(0 , 0 , size , l , r);
    }
};


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    po1[0] = po2[0] = 1;
    pref1[0] = pref2[0] = 1;
    for(int i = 1 ; i < MXN ; i++) {
        po1[i] = po1[i-1] * PR1 % MOD1;
        po2[i] = po2[i-1] * PR2 % MOD2;
        pref1[i] = (po1[i] + pref1[i-1]) % MOD1;
        pref2[i] = (po2[i] + pref2[i-1]) % MOD2;
    }

    cin >> n;
    for(int i = 0 ; i < 3 ; i++) {
        string s; cin >> s;
        for(auto c : s) {
            str[i].push_back(c == 'J' ? 0 : (c == 'O' ? 1 : 2));
        }
    }
    prep(0 , 0 , 1); prep(0 , 1 , 0); prep(0 , 2 , 2);
    prep(1 , 0 , 0); prep(1 , 1 , 2); prep(1 , 2 , 1);
    prep(2 , 0 , 2); prep(2 , 1 , 1); prep(2 , 2 , 0);

    cin >> q;
    string s; cin >> s;
    vector<int> v;
    for(auto c : s) {
        v.push_back(c == 'J' ? 0 : (c == 'O' ? 1 : 2));
    }

    seg_tree seg;
    seg.init(); seg.build(v);
    cout << (H.count(Hash(v)) ? "Yes\n" : "No\n");

    while(q--) {

        int l , r;
        char c;
        cin >> l >> r >> c; l--;
        seg.set(l , r , (c == 'J' ? 0 : (c == 'O' ? 1 : 2)));
        pair<ll,ll> h = seg.hsh[0];
        cout << (H.count(h) ? "Yes\n" : "No\n");
    }
}

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