Submission #1132066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132066		NoMercy	Crossing (JOI21_crossing)	C++20	26 / 100	333 ms	26744 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
struct Lazy_Segtree {
    #define left v + 1
    #define right v + 2 * (tm - tl)
    struct pi {
        ll sum = 0, lazy = 0, mark = 0;
    } emp;
    vector<pi> tree;
    vector<ll> pw, pref;
    void init (int x, int p) {
        tree.assign (x << 1, emp);
        pw.assign (x + 2, 1);
        pref.assign (x + 2, 0);
        for (int i = 1;i <= x + 1;i ++) pw[i] = (pw[i - 1] * p) % mod, pref[i] = (pref[i - 1] + pw[i - 1]) % mod;
    }

    void built (int v, int tl, int tr, string& arr) {
        if (tl + 1 == tr) {
            tree[v].sum = (((arr[tl] == 'J' ? 3 : 0) + (arr[tl] == 'O' ? 2 : 0) + (arr[tl] == 'I' ? 1 : 0)) * pw[tl]) % mod;
            return;
        }
        int tm = (tl + tr) >> 1;
        built (left, tl, tm, arr);
        built (right, tm, tr, arr);
        tree[v].sum = (tree[left].sum + tree[right].sum) % mod;
    }
    void push (int v, int tl, int tr) {
        if (tl + 1 == tr || tree[v].mark == 0) return;
        int tm = (tl + tr) >> 1;
        assert (tree[v].lazy > 0);
        tree[left].lazy = tree[right].lazy = tree[v].lazy;
        tree[left].mark = tree[right].mark = 1;
        tree[left].sum = (tree[v].lazy * (pref[tm] - pref[tl] + mod % mod)) % mod;
        tree[right].sum = (tree[v].lazy * (pref[tr] - pref[tm] + mod % mod)) % mod;
        tree[v].lazy = tree[v].mark = 0;
    }
    void update (int v, int tl, int tr, int ql, int qr, ll val) {
        if (ql >= tr || tl >= qr) {
            return;
        }
        if (ql <= tl && tr <= qr) {
            assert (val > 0);
            tree[v].sum = (val * (pref[tr] - pref[tl] + mod % mod)) % mod;
            tree[v].lazy = val;
            tree[v].mark = 1;
            return;
        } 
        push (v, tl, tr);
        int tm = (tl + tr) >> 1;
        update (left, tl, tm, ql, qr, val);
        update (right, tm, tr, ql, qr, val);
        tree[v].sum = (tree[left].sum + tree[right].sum + mod) % mod;
    }
    ll get (int v, int tl, int tr, int ql, int qr) {
        if (tl >= qr || ql >= tr) {
            return 0LL;
        }
        if (ql <= tl && tr <= qr) {
            return tree[v].sum;
        }
        push (v, tl, tr);
        int tm = (tl + tr) >> 1;
        return (get (left, tl, tm, ql, qr) + get (right, tm, tr, ql, qr) + mod) % mod;
    }
};

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N;
    cin >> N;
    string S;
    cin >> S;
    cin >> S;
    cin >> S;    
    int Q;
    cin >> Q;
    string T;
    cin >> T;
    Lazy_Segtree ST1, ST2;
    ST1.init (N + 2, 7);
    ST1.built (0, 0, N, T);
    ST2.init (N + 2, 9);
    ST2.built (0, 0, N, T);
    ll hs1 = 0, hs2 = 0;
    for (int i = 0;i < N;i ++) {
        hs1 = (hs1 + (ST1.pw[i] * ((S[i] == 'J' ? 3 : 0) + (S[i] == 'O' ? 2 : 0) + (S[i] == 'I' ? 1 : 0)) % mod)) % mod;
        hs2 = (hs2 + (ST2.pw[i] * ((S[i] == 'J' ? 3 : 0) + (S[i] == 'O' ? 2 : 0) + (S[i] == 'I' ? 1 : 0)) % mod)) % mod;
    }

    ((ST1.tree[0].sum + mod % mod) == (hs1 + mod % mod) && (ST2.tree[0].sum + mod % mod) == (hs2 % mod) ? cout << "Yes\n" : cout << "No\n");
    while (Q --) {
        int l, r;
        cin >> l >> r;
        char ch;
        cin >> ch;
        -- l;
        ST1.update (0, 0, N, l, r, ((ch == 'J' ? 3 : 0) + (ch == 'O' ? 2 : 0) + (ch == 'I' ? 1 : 0)));
        ST2.update (0, 0, N, l, r, ((ch == 'J' ? 3 : 0) + (ch == 'O' ? 2 : 0) + (ch == 'I' ? 1 : 0)));
        ((ST1.tree[0].sum + mod % mod) == (hs1 + mod % mod) && (ST2.tree[0].sum + mod % mod) == (hs2 % mod) ? cout << "Yes\n" : cout << "No\n");
    }
}

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