Submission #1228829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228829		meth_enjoyer	Crossing (JOI21_crossing)	C++20	26 / 100	170 ms	17824 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxN = 2e5 + 5;
const ll mod = 1e9 + 433;
const ll base = 31;
int n, q;
string s[4], t;
ll p[maxN], sum[maxN];

void init(){
    p[0] = 1;
    for (int i = 1; i <= n; ++i){
        p[i] = p[i - 1] * base % mod;
        sum[i] = (sum[i - 1] + p[i - 1]) % mod;
    }
}

ll cong(ll a, ll b){
    return (a % mod + b % mod) % mod;
}

ll nhan(ll a, ll b){
    return a % mod * b % mod;
}

ll tru(ll a, ll b){
    return (a - b + mod * (a - b < 0));
}

ll get_hash(string& f){
    ll res = 0;
    for (const auto& x : f){
        res = res * base + x;
        res%= mod;
    }
    return res;
}

struct seg{
    vector<ll> st, lazy;

    seg(int n = 0) {
        st.assign(n << 2 | 3, 0);
        lazy.assign(n << 2 | 3, 0);
    }

    void down(int id, int l, int mid, int r){
        ll val = lazy[id];
        if (!val) return;
        lazy[id << 1] = lazy[id << 1 | 1] = val;

        st[id << 1] = nhan(val, sum[mid - l + 1]);
        st[id << 1 | 1] = nhan(val, sum[r - mid]);
        lazy[id] = 0;
    }

    ll set_val(ll a, ll b, int len){
        return cong(nhan(a, p[len]), b);
    }

    void build(int id, int l, int r, string& f){
        if (l == r){
            st[id] = f[l - 1];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, f);
        build(id << 1 | 1, mid + 1, r, f);
        st[id] = set_val(st[id << 1], st[id << 1 | 1], r - mid);
    }

    void update(int id, int l, int r, int u, int v, int val){
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            st[id] = nhan(val, sum[r - l + 1]);
            lazy[id] = val;
            return;
        }

        int mid = (l + r) >> 1;
        down(id, l, mid, r);

        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = set_val(st[id << 1], st[id << 1 | 1], r - mid);
    }

};

seg st(maxN);

void solve(){
    st.build(1, 1, n, t);
    ll temp = get_hash(s[1]);
    if (st.st[1] == temp)
        cout << "Yes";
    else
        cout << "No";
    cout << '\n';
    while (q--){
        int l, r;
        char val;
        cin >> l >> r >> val;
        st.update(1, 1, n, l, r, val);
        if (st.st[1] == temp)
            cout << "Yes";
        else
            cout << "No";
        cout << '\n';
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
//    freopen("a.inp", "r", stdin);
//    freopen("a.out", "w", stdout);
    cin >> n;
    for (int i = 1; i < 4; ++i)
        cin >> s[i];
    cin >> q;
    cin >> t;
    init();
    solve();
    return 0;
}

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