Submission #420677

#	Time	Username	Problem	Language	Result	Execution time	Memory
420677		kwongweng	Crossing (JOI21_crossing)	C++17	100 / 100	1184 ms	31040 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

ll MOD = 1000000007;
ll A = 998244353;

ll power(ll base, ll n){
    if (n == 0) return 1;
    if (n == 1) return base;
    ll halfn = power(base, n/2);
    if (n%2 == 0) return (halfn*halfn)%MOD;
    return (((halfn*halfn)%MOD)*base) % MOD;
}

ll inverse(ll n){
    return power(n, MOD-2);
}

ll add(ll a, ll b){
    return (a+b) % MOD;
}

ll mul(ll a, ll b){
    return (a*b) % MOD;
}

ll gcd(ll a, ll b){
    if (a == 0) return b;
    if (a == 1) return 1;
    return gcd(b%a, a);
}

ll p[200001], pre[200001];
struct segtree{
    int sz; vector<ll> hash, as;
    void init(int n){
        sz = n;
        hash.assign(4*n, 0);
        as.assign(4*n, -1);
    }
    void prop(int v, int tl, int tr){
        if (as[v] == -1) return;
        if (tl == tr){
            return;
        }
        int tm = (tl + tr)/2;
        as[2*v] = as[v];
        as[2*v+1] = as[v];
        hash[2*v] = mul(as[v], pre[tm-tl]);
        hash[2*v+1] = mul(as[v], pre[tr-tm-1]);
        as[v] = -1;
    }
    void update(int v, int tl, int tr, int l, int r, ll val){
        prop(v, tl, tr);
        if (tl == l && tr == r){
            as[v] = val;
            hash[v] = mul(as[v], pre[tr-tl]);
            return;
        }
        if (l > r) return;
        int tm = (tl + tr)/2;
        update(2*v, tl, tm, l, min(r, tm), val);
        update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
        hash[v] = add(mul(hash[2*v], p[tr-tm]), hash[2*v+1]);
    }
    void update(int l, int r, ll val){
        update(1, 0, sz-1, l, r, val);
    }
};

map<char, int> joi;
string JOI = "JOI";
ll Hash(string s){
    ll ans = 0;
    int sz = s.size();
    FOR(i, 0, sz){
        ans = mul(ans, A);
        ans += joi[s[i]];
    }
    return ans;
}

string comb(string a, string b){
    string ans = "";
    int sz = a.size();
    FOR(i, 0, sz){
        ans += JOI[(6-joi[a[i]]-joi[b[i]]) % 3];
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    pre[0] = 1; p[0] = 1;
    FOR(i, 1, 200001){
        p[i] = mul(p[i-1], A);
        pre[i] = add(pre[i-1], p[i]);
    }
    joi['J'] = 0;
    joi['O'] = 1;
    joi['I'] = 2; 
    int n; cin >> n;
    string s1, s2, s3; cin >> s1 >> s2 >> s3;
    map<ll, int> mp;
    mp[Hash(s1)] = 1;
    mp[Hash(s2)] = 1;
    mp[Hash(s3)] = 1;
    string a1 = comb(s1, s2);
    string a2 = comb(s2, s3);
    string a3 = comb(s3, s1);
    mp[Hash(a1)] = 1;
    mp[Hash(a2)] = 1;
    mp[Hash(a3)] = 1;
    string b1 = comb(a1, s3);
    string b2 = comb(a2, s1);
    string b3 = comb(a3, s2);
    mp[Hash(b1)] = 1;
    mp[Hash(b2)] = 1;
    mp[Hash(b3)] = 1;
    segtree st;
    st.init(n);
    int q; cin >> q;
    string t; cin >> t;
    FOR(i, 0, n){
        st.update(i, i, joi[t[i]]);
    }
    if (mp[st.hash[1]]) cout << "Yes\n";
    else cout << "No\n";
    while (q--){
        int l, r; cin >> l >> r;
        char c; cin >> c;
        st.update(l-1, r-1, joi[c]);
        if (mp[st.hash[1]]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

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