Submission #542265

#	Time	Username	Problem	Language	Result	Execution time	Memory
542265		radal	Crossing (JOI21_crossing)	C++17	100 / 100	625 ms	17708 KiB

Main

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr ll N = 2e5+20,mod = 1e9+9,inf = 1e9+10,mod2 = 1e9+7,mod3 = 1e9+21;
inline int mkay(int a,int b,int mod){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k,int m){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%m;
        a = 1ll*a*a%m;
        k >>= 1;
    }
    return z;
}
int pw[N][3],n;
set <pair<int,pll> >st;
int lz[N*4],inv[3];
pair<int,pll> seg[N*4];
inline string Xor(string& s,string& t){
    string ans = "";
    rep(i,0,n){
        if (s[i] == t[i]) ans += s[i];
        else{
            if (s[i] != 'J' && t[i] !='J') ans += 'J';
            else if (s[i] != 'O' && t[i] != 'O') ans += 'O';
            else ans += 'I';
        }
    }
    return ans;
}
inline int hash_func(string& s,int f,int m){
    int ans = 0;
    rep(i,0,n){
        if (s[i] == 'J') continue;
        if (s[i] == 'O')
            ans = mkay(ans,pw[i][f],m);
        else
            ans = mkay(ans,pw[i][f]*2%m,m);
    }
    return ans;
}
string t;

void build(int l = 0,int r = n,int v = 1){
    lz[v] = -1;
    if (r-l == 1){
        if(t[l] == 'J'){
            seg[v] = {0,{0,0}};
            return;
        }
        if (t[l] == 'O'){
            seg[v] = {pw[l][0],{pw[l][1],pw[l][2]}};
            return;
        }
        seg[v] = {mkay(pw[l][0],pw[l][0],mod),{mkay(pw[l][1],pw[l][1],mod2),mkay(pw[l][2],pw[l][2],mod3)}};
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    seg[v].X = mkay(seg[u].X,seg[u|1].X,mod);
    seg[v].Y.X = mkay(seg[u].Y.X,seg[u|1].Y.X,mod2);
    seg[v].Y.Y = mkay(seg[u].Y.Y,seg[u|1].Y.Y,mod3);
}

inline void pass(int l,int r,int v){
    if (lz[v] == -1) return;
    int u = (v << 1);
    lz[u] = lz[v];
    lz[u|1] = lz[v];
    if (lz[v] == 0){
        seg[u] = {0,{0,0}};
        seg[u|1] = {0,{0,0}};
        lz[v] = -1;
        return;
    }
    int m = (l+r) >> 1;
    int L[3], R[3];
    R[0] = mkay(pw[r][0],-pw[m][0],mod);
    R[1] = mkay(pw[r][1],-pw[m][1],mod2);
    R[2] = mkay(pw[r][2],-pw[m][2],mod3);
    L[0] = mkay(pw[m][0],-pw[l][0],mod);
    L[1] = mkay(pw[m][1],-pw[l][1],mod2);
    L[2] = mkay(pw[m][2],-pw[l][2],mod3);
    if (lz[v] == 2){
        seg[u] = {L[0],{L[1],L[2]}};
        seg[u|1] = {R[0],{R[1],R[2]}};
        lz[v] = -1;
        return;
    }
    lz[v] = -1;
    L[0] = 1ll*L[0]*inv[0]%mod;
    R[0] = 1ll*R[0]*inv[0]%mod;
    L[1] = 1ll*L[1]*inv[1]%mod2;
    R[1] = 1ll*R[1]*inv[1]%mod2;
    L[2] = 1ll*L[2]*inv[2]%mod3;
    R[2] = 1ll*R[2]*inv[2]%mod3;
    seg[u] = {L[0],{L[1],L[2]}};
    seg[u|1] = {R[0],{R[1],R[2]}};
}

void upd(int l,int r,int s,int e,int x,int v = 1){
    if (s >= r || l >= e) return;
    if (s <= l && r <= e){
        lz[v] = x;
        if (!x){
            seg[v] = {0,{0,0}};
            return;
        }
        if (x == 2){
            seg[v].X = mkay(pw[r][0],-pw[l][0],mod);
            seg[v].Y.X = mkay(pw[r][1],-pw[l][1],mod2);
            seg[v].Y.Y = mkay(pw[r][2],-pw[l][2],mod3);
            return;
        }
        seg[v].X = 1ll*mkay(pw[r][0],-pw[l][0],mod)*inv[0]%mod;
        seg[v].Y.X = 1ll*mkay(pw[r][1],-pw[l][1],mod2)*inv[1]%mod2;
        seg[v].Y.Y = 1ll*mkay(pw[r][2],-pw[l][2],mod3)*inv[2]%mod3;
        return;
    }
    pass(l,r,v);
    int u = (v << 1),m = (l+r) >> 1;
    upd(l,m,s,e,x,u);
    upd(m,r,s,e,x,u|1);
    seg[v].X = mkay(seg[u].X,seg[u|1].X,mod);
    seg[v].Y.X = mkay(seg[u].Y.X,seg[u|1].Y.X,mod2);
    seg[v].Y.Y = mkay(seg[u].Y.Y,seg[u|1].Y.Y,mod3);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n;
    set<string> st2;
    inv[0] = poww(2,mod-2,mod);
    inv[1] = poww(2,mod2-2,mod2);
    inv[2] = poww(2,mod3-2,mod3);
    rep(i,0,3){
        string s;
        cin >> s;
        st2.insert(s);
    }
    rep(i,0,1000){
        bool f = 0;
        for (string s : st2){
            for (string v : st2){
                string w = Xor(s,v);
                if (st2.find(w) != st2.end()) continue;
                f = 1;
                st2.insert(w);
            }
        }
        if (!f) break;
    }
    pw[0][0] = pw[0][1] = pw[0][2] = 1;
    rep(i,1,n+3){
        pw[i][0] = 1ll*pw[i-1][0]*3%mod;
        pw[i][1] = 1ll*pw[i-1][1]*3%mod2;
        pw[i][2] = 1ll*pw[i-1][2]*3%mod3;
    }
    for (string s : st2){
        st.insert({hash_func(s,0,mod),{hash_func(s,1,mod2),hash_func(s,2,mod3)}});
    }
    cin >> q;
    cin >> t;
    build();
    if (st.find(seg[1]) != st.end()){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    while (q--){
        int l,r;
        char c;
        cin >> l >> r >> c;
        l--;
        if (c == 'J') upd(0,n,l,r,0);
        if (c == 'O') upd(0,n,l,r,1);
        if (c == 'I') upd(0,n,l,r,2);
        cout << ((st.find(seg[1]) != st.end()) ? "Yes" : "No") << endl;
    }
}

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