Submission #1142789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142789		antonn	Crossing (JOI21_crossing)	C++20	100 / 100	247 ms	15192 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

set<string> v;

string cross(string a, string b) {
    string c = a;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == b[i]) c[i] = a[i];
        else c[i] = a[i] ^ b[i] ^ 'J' ^ 'O' ^ 'I';
    }
    return c;
}

void bkt(string s) {
    for (auto x : v) {
        if (!v.count(cross(x, s))) {
            v.insert(cross(x, s));
            // cout << cross(x, s) << "\n";
            bkt(cross(x, s));
        }
    }
}

string check(string t) {
    bool ok = 0;
    for (auto x : v) {
        if (x == t) {
            ok = 1;
        }
    }
    return (ok ? "Yes" : "No");
}

const int M = 1e9 + 7;
const int B = 257;

int mul(int a, int b) {
    return (ll) a * b % M;
}

int add(int a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
    return a;
}

int pw(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = mul(r, a);
        a = mul(a, a);
        b >>= 1;
    }
    return r;
}

string t;

int f(string s) {
    int b = 0;
    for (auto x : s) {
        b = mul(b, B);
        b = add(b, x);
    }
    return b;
}

struct T {
    int hsh;
    int len;
};

const int N = 2e5 + 7;

T tree[4 * N];
int lazy[4 * N];

int INV = pw(B - 1, M - 2);
int pwB[N];

int progr(int x) {
    return mul(add(pwB[x], -1), INV);
}

T join(T a, T b) {
    T c;
    c.len = a.len + b.len;
    c.hsh = add(mul(a.hsh, pwB[b.len]), b.hsh);
    return c;
}

void push(int v, int tl, int tr) {
    if (lazy[v] == 0) return;
    if (tl < tr) lazy[2 * v] = lazy[2 * v + 1] = lazy[v];

    tree[v].hsh = mul(lazy[v], progr(tree[v].len));
    lazy[v] = 0;
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = {t[tl - 1], 1};
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        tree[v] = join(tree[2 * v], tree[2 * v + 1]);
    }
}

void setRange(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        lazy[v] = x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    setRange(2 * v, tl, tm, l, r, x);
    setRange(2 * v + 1, tm + 1, tr, l, r, x);
    tree[v] = join(tree[2 * v], tree[2 * v + 1]);
}

T get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (l > tr || r < tl) return {0, 0};
    if (l <= tl && tr <= r) return tree[v];

    int tm = (tl + tr) / 2;
    return join(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}

int n;
set<int> hs;

string resp() {
    bool ok = hs.count(get(1, 1, n, 1, n).hsh);
    // cout << "! " << get(1, 1, n, 1, n).hsh << "\n";
    return (ok ? "Yes" : "No");
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    string a, b, c; cin >> a >> b >> c;
    v.insert(a);
    v.insert(b);
    v.insert(c);
    bkt(a);
    bkt(b);
    bkt(c);

    for (auto x : v) hs.insert(f(x));

    pwB[0] = 1;
    for (int i = 1; i < N; ++i) pwB[i] = mul(pwB[i - 1], B);

    int q; cin >> q;
    cin >> t;
    build(1, 1, n);
    cout << resp() << "\n";
    for (int i = 1; i <= q; ++i) {
        int l, r; char c; cin >> l >> r >> c;
        setRange(1, 1, n, l, r, c);

        cout << resp() << "\n";
    }
}

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