Submission #1132065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132065		NoMercy	Crossing (JOI21_crossing)	C++20	100 / 100	411 ms	30708 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 + 3, 1);
        pref.assign (x + 3, 0);
        for (int i = 1;i < x + 3;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)) % mod;
        tree[right].sum = (tree[v].lazy * ((pref[tr] - pref[tm] + mod + 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)) % 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;
    }
};

string calculate (string a,string b,string rs=""){
    for (int i = 0;i < (int)a.size();i ++) {
        if (a[i] == b[i]) rs += a[i];
        else rs += char('J'+'O'+'I'-a[i]-b[i]);
    }
    return rs;
}

int32_t main () {

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

    int N;
    cin >> N;
    string S;
    vector<string> ans;
    map<string, bool> used;
    cin >> S; used[S] = 1;
    ans.push_back(S);
    cin >> S; used[S] = 1;
    ans.push_back(S);
    cin >> S; used[S] = 1;
    ans.push_back(S);
    int Q;
    cin >> Q;
    string T;
    cin >> T;
    Lazy_Segtree ST1, ST2;
    ST1.init (N + 2, 17);
    ST1.built (0, 0, N, T);
    ST2.init (N + 2, 17);
    ST2.built (0, 0, N, T);
    for (int i = 0;i < ans.size();i ++) {
        for (int j = 0;j < ans.size();j ++) {
            string rs = calculate (ans[i], ans[j]);
            if (used.find(rs) == used.end()) used[rs] = 1, ans.push_back(rs);
        }
    }
    // cout << ans.size() << "\n";
    vector<ll> hs1(ans.size(), 0), hs2(ans.size(), 0);
    for (int i = 0;i < ans.size();i ++) {
        for (int j = 0;j < N;j ++) {
            hs1[i] = (hs1[i] + (((ans[i][j] == 'J' ? 3 : 0) + (ans[i][j] == 'O' ? 2 : 0) + (ans[i][j] == 'I' ? 1 : 0)) * ST1.pw[j])) % mod;
            hs2[i] = (hs2[i] + (((ans[i][j] == 'J' ? 3 : 0) + (ans[i][j] == 'O' ? 2 : 0) + (ans[i][j] == 'I' ? 1 : 0)) * ST2.pw[j])) % mod;
        }
    }
    auto print = [&]() -> void {
        for (int i = 0;i < ans.size();i ++) {
            if ((ST1.get (0, 0, N, 0, N) + mod) % mod == (hs1[i] + mod) % mod && (ST2.get (0, 0, N, 0, N) + mod) % mod == (hs2[i] + mod) % mod) {
                cout << "Yes\n";
                return;
            }
            // if (T == ans[i]) {
            //     cout << "Yes\n";
            //     return;
            // }
        }
        cout << "No\n";
    };
    print ();
    while (Q --) {
        int l, r;
        cin >> l >> r;
        char ch;
        cin >> ch;
        -- l;
        // for (int i = l;i < r;i ++) T[i] = ch;
        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)));
        print ();
    }
}

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