Submission #927936

#	Time	Username	Problem	Language	Result	Execution time	Memory
927936		TAhmed33	Crossing (JOI21_crossing)	C++98	100 / 100	844 ms	46848 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int __int128
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MOD = (1ll << 61) - 1;
const int b = 1e9 + 7;
map <char, int> ll = {
    {'J', 0},
    {'O', 1},
    {'I', 2}
}; 
long long n;
const int MAXN = 200025;
int pw[MAXN];
int inv[MAXN];
int sub (int a, int b) {
    if (!b) return pw[a];
    return (pw[a] - pw[b - 1] + MOD) % MOD;
}
struct SegmentTree {
    int tree[2 * MAXN], lazy[2 * MAXN];
    void prop (int l, int r, int node) {
        if (-1 == lazy[node]) return;
        if (l == r) {
            tree[node] = (lazy[node] * sub(l, l)) % MOD;
            lazy[node] = -1;
            return;
        }
        lazy[tl] = lazy[tr] = lazy[node];
        tree[node] = (lazy[node] * sub(r, l)) % MOD;
        lazy[node] = -1;
    }
    void update (int l, int r, int a, int b, int c, int node) {
        prop(l, r, node);
        if (l > b || r < a) return;
        if (l >= a && r <= b) {
            lazy[node] = c;
            prop(l, r, node);
            return;
        }  
        update(l, mid, a, b, c, tl);
        update(mid + 1, r, a, b, c, tr);
        tree[node] = (tree[tl] + tree[tr]) % MOD;
    }
    int get (int l, int r, int a, int b, int node) {
        prop(l, r, node);
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return tree[node];
        return (get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr)) % MOD;
    }
} cur;
int power (int a, int b) {
    if (!b) return 1;
    int u = power(a, b >> 1);
    u = (u * u) % MOD;
    if (b & 1) u = (u * a) % MOD;
    return u;
}
int hashh (vector <int> a) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (sum + (a[i] * sub(i, i)) % MOD) % MOD;
    }
    return sum;
} 
vector <int> merge (vector <int> a, vector <int> b) {
    vector <int> c;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            c.push_back(a[i]);
        } else {
            set <int> u = {0, 1, 2};
            u.erase(a[i]);
            u.erase(b[i]);
            int x = *(u.begin());
            c.push_back(x);
        }
    }
    return c;
}
set <int> ok;
void answer () {
    if (ok.count(cur.get(0, n - 1, 0, n - 1, 1))) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}
signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(cur.lazy, -1, sizeof(cur.lazy));
    pw[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pw[i] = (b * pw[i - 1]) % MOD;
    }
    inv[MAXN - 1] = power(pw[MAXN - 1], MOD - 2);
    for (int i = 1; i < MAXN; i++) {
        pw[i] = (pw[i] + pw[i - 1]) % MOD;
    }
    for (int i = MAXN - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * b) % MOD;
    }
    cin >> n;
    vector <int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        char x;
        cin >> x;
        a[i] = ll[x];
    }
    for (int i = 0; i < n; i++) {
        char x;
        cin >> x;
        b[i] = ll[x];
    }
    for (int i = 0; i < n; i++) {
        char x;
        cin >> x;
        c[i] = ll[x];
    }
    ok.insert(hashh(a));
    ok.insert(hashh(b));
    ok.insert(hashh(c));
    ok.insert(hashh(merge(a, b)));
    ok.insert(hashh(merge(a, c)));
    ok.insert(hashh(merge(b, c)));
    ok.insert(hashh(merge(merge(a, b), c)));
    ok.insert(hashh(merge(merge(a, c), b)));
    ok.insert(hashh(merge(merge(b, c), a)));
    long long q;
    cin >> q;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        cur.update(0, n - 1, i, i, ll[s[i]], 1);
    }
    answer();
    for (int i = 0; i < q; i++) {
        long long l, r;
        cin >> l >> r;
        char x;
        cin >> x;
        int z = ll[x];
        cur.update(0, n - 1, l - 1, r - 1, z, 1);
        answer();
    }
}

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