Submission #887148

#	Time	Username	Problem	Language	Result	Execution time	Memory
887148		box	Crossing (JOI21_crossing)	C++17	100 / 100	719 ms	34492 KiB

Main

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

mt19937 rng(1234);

string gen(int n) {
    string s(n, '?');
    for (int i = 0; i < n; i++) s[i] = "JOI"[rng() % 3];
    return s;
}

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 2e5, N_ = 1 << 18, K = 9;

string operator+(string one, const string two) {
    static char all = 'J' ^ 'O' ^ 'I';
    for (int i = 0; i < sz(one); i++)
        one[i] = one[i] == two[i] ? one[i] : (one[i] ^ two[i] ^ all);
    return one;
}

int id(char c) {
    return c == 'J' ? 0 : c == 'O' ? 1 : 2;
}

i64 hsh(const string s) {
    static const int P1 = 1e9 + 7, P2 = 1e9 + 9;
    i64 one = 0, two = 0;
    for (char c : s) {
        one = (one * 3 + id(c)) % P1;
        two = (two * 3 + id(c)) % P2;
    }
    return one * P2 + two;
}

int n, q;
vector<string> v;
unordered_set<i64> s;

void expand() {
    for (string t : v) s.insert(hsh(t));
    while (1) {
        int m = sz(v);
        for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) {
            string t = v[i] + v[j];
            i64 h = hsh(t);
            if (!s.count(h)) {
                s.insert(h);
                v.push_back(t);
            }
        }
        if (sz(v) == m) break;
    }
}

ar<int, 3> pf[K][N + 1];
bitset<K> ok[N_ * 2];
int lz[N_ * 2];

bool filled(int t, int l, int r, int c) {
    return pf[t][r + 1][c] - pf[t][l][c] == r - l + 1;
}

void bld(int k, int l, int r, string &s) {
    lz[k] = -1;
    if (l == r) {
        for (int t = 0; t < sz(v); t++)
            ok[k][t] = filled(t, l, l, id(s[l]));
    } else {
        int m = (l + r) / 2;
        bld(k * 2, l, m, s), bld(k * 2 + 1, m + 1, r, s);
        ok[k] = ok[k * 2] & ok[k * 2 + 1];
    }
}

void put(int k, int l, int r, int c) {
    for (int t = 0; t < sz(v); t++)
        ok[k][t] = filled(t, l, r, c);
    lz[k] = c;
}

void push(int k, int l, int r) {
    if (~lz[k]) {
        int m = (l + r) / 2;
        put(k * 2, l, m, lz[k]), put(k * 2 + 1, m + 1, r, lz[k]);
        lz[k] = -1;
    }
}

void upd(int k, int l, int r, int ql, int qr, int c) {
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) return void(put(k, l, r, c));
    int m = (l + r) / 2;
    push(k, l, r);
    upd(k * 2, l, m, ql, qr, c), upd(k * 2 + 1, m + 1, r, ql, qr, c);
    ok[k] = ok[k * 2] & ok[k * 2 + 1];
}

bool qry() {
    return ok[1].count();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int rep = 0; rep < 3; rep++) {
        string s;
        cin >> s;
        v.push_back(s);
    }
    expand();
    for (int t = 0; t < sz(v); t++) for (int i = 0; i < n; i++) {
        pf[t][i + 1] = pf[t][i];
        pf[t][i + 1][id(v[t][i])]++;
    }
    cin >> q;
    string t;
    cin >> t;
    bld(1, 0, n - 1, t);
    cout << (qry() ? "Yes\n" : "No\n");
    while (q--) {
        int l, r; char c;
        cin >> l >> r >> c, l--, r--;
        upd(1, 0, n - 1, l, r, id(c));
        cout << (qry() ? "Yes\n" : "No\n");
    }
}

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