Submission #951671

#	Time	Username	Problem	Language	Result	Execution time	Memory
951671		arbuzick	Crossing (JOI21_crossing)	C++17	0 / 100	167 ms	10836 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1e9 + 7, base = 3;

constexpr int R = 1 << 18;

int pw[R * 2], pr_sum[R * 2 + 1];

int val[R * 2], psh[R * 2];

void build() {
    pw[0] = 1;
    for (int i = 1; i < R * 2; ++i) {
        pw[i] = pw[i - 1] * 1LL * base % mod;
    }
    pr_sum[0] = 0;
    for (int i = 0; i < R * 2; ++i) {
        pr_sum[i + 1] = (pr_sum[i] + pw[i]) % mod;
    }
    for (int i = 1; i < R * 2; ++i) {
        psh[i] = -1;
    }
}

void push(int node, int nl, int nm, int nr) {
    if (psh[node] != -1) {
        val[node * 2] = pr_sum[nm - nl] * 1LL * psh[node] % mod;
        psh[node * 2] = psh[node];
        val[node * 2 + 1] = pr_sum[nr - nm] * 1LL * psh[node] % mod;
        psh[node * 2 + 1] = psh[node];
    }
    psh[node] = -1;
}

void assign(int ql, int qr, int vl, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        val[node] = pr_sum[nr - nl] * 1LL * vl % mod;
        psh[node] = vl;
        return;
    }
    if (qr <= nl || nr <= ql) {
        return;
    }
    int nm = (nl + nr) / 2;
    push(node, nl, nm, nr);
    assign(ql, qr, vl, node * 2, nl, nm);
    assign(ql, qr, vl, node * 2 + 1, nm, nr);
    val[node] = (val[node * 2] * 1LL * pw[nr - nm] + val[node * 2 + 1]) % mod;
}

int get(int ql, int qr, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        return val[node];
    }
    if (qr <= nl || nr <= ql) {
        return 0;
    }
    int nm = (nl + nr) / 2;
    push(node, nl, nm, nr);
    int hash1 = get(ql, qr, node * 2, nl, nm), hash2 = get(ql, qr, node * 2 + 1, nm, nr);
    val[node] = (val[node * 2] * 1LL * pw[nr - nm] + val[node * 2 + 1]) % mod;
    int len2 = max(0, min(nr, qr) - max(nm, ql));
    return (hash1 * 1LL * pw[len2] + hash2) % mod;
}

void solve() {
    build();
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    map<char, int> vl;
    vl['J'] = 0;
    vl['O'] = 1;
    vl['I'] = 2;
    auto cross = [&](string a, string b) {
        string c = "";
        for (int i = 0; i < n; ++i) {
            if (a[i] == b[i]) {
                c += a[i];
            } else {
                if (a[i] != 'J' && b[i] != 'J') {
                    c += 'J';
                } else if (a[i] != 'O' && b[i] != 'O') {
                    c += 'O';
                } else {
                    c += 'I';
                }
            }
        }
        return c;
    };
    auto get_hash = [&](string a) {
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = (ans * 1LL * base + vl[a[i]]) % mod;
        }
        return ans;
    };
    vector<string> nw = {a, b, c};
    set<int> used;
    used.insert(get_hash(a));
    used.insert(get_hash(b));
    used.insert(get_hash(c));
    for (int i = 0; i < (int)nw.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            string add = cross(nw[i], nw[j]);
            int hash_nw = get_hash(add);
            if (!used.count(hash_nw)) {
                used.insert(hash_nw);
                nw.push_back(add);
            }
        }
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    for (int i = 0; i < n; ++i) {
        assign(i, i + 1, vl[t[i]]);
    }
    if (used.count(get(0, n))) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    while (q--) {
        int l, r;
        char ch;
        cin >> l >> r >> ch;
        l--;
        assign(l, r, vl[ch]);
        if (used.count(get(0, n))) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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