Submission #1148679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148679		trufanov.p	Crossing (JOI21_crossing)	C++20	100 / 100	211 ms	23008 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

typedef long long ll;

const ll p = 179;
const ll Mod = 1e9 + 7;

vector<ll> powers;
vector<vector<ll>> hashone;

inline int toi(char c) {
    if (c == 'J') {
        return 1;
    } else if (c == 'O') {
        return 2;
    } else {
        return 3;
    }
}

inline char toc(int x) {
    if (x == 1) {
        return 'J';
    } else if (x == 2) {
        return 'O';
    } else {
        return 'I';
    }
}

void precalc(int n) {
    powers.resize(n + 1);
    powers[0] = 1;
    for (int i = 1; i <= n; ++i) {
        powers[i] = (powers[i - 1] * p) % Mod;
    }
    hashone.resize(4, vector<ll>(n + 1));
    for (int i = 1; i < 4; ++i) {
        hashone[i][1] = i;
        for (int j = 2; j <= n; ++j) {
            hashone[i][j] = (hashone[i][j - 1] * p + i) % Mod;
        }
    }
}

string combine(const string& A, const string& B) {
    string res = "";
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        res += toc(2 * (toi(A[i]) - 1 + toi(B[i]) - 1) % 3 + 1);
    }
    return res;
}

ll calcHash(const string& g) {
    ll h = 0;
    for (char c : g) {
        h = (h * p + toi(c)) % Mod;
    }
    return h;
}

vector<ll> t;
vector<ll> c;
vector<bool> has;

void push(int v) {
    if (has[v]) {
        c[2 * v + 1] = c[v];
        c[2 * v + 2] = c[v];
        has[2 * v + 1] = true;
        has[2 * v + 2] = true;
        has[v] = false;
    }
}

void build(int v, int l, int r, const string& s) {
    if (l == r - 1) {
        t[v] = toi(s[l]);
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m, s);
    build(2 * v + 2, m, r, s);
    t[v] = ((t[2 * v + 1] * powers[r - m]) % Mod + t[2 * v + 2]) % Mod;
}

void update(int v, int l, int r, int askl, int askr, int val) {
    if (l >= askr || r <= askl) {
        return;
    }
    if (l >= askl && r <= askr) {
        c[v] = val;
        has[v] = true;
        return;
    }
    push(v);
    int m = (l + r) / 2;
    update(2 * v + 1, l, m, askl, askr, val);
    update(2 * v + 2, m, r, askl, askr, val);
    ll vall = (has[2 * v + 1] ? hashone[c[2 * v + 1]][m - l] : t[2 * v + 1]);
    ll valr = (has[2 * v + 2] ? hashone[c[2 * v + 2]][r - m] : t[2 * v + 2]);
    t[v] = ((vall * powers[r - m]) % Mod + valr) % Mod;
}

inline ll query(int n) {
    return (has[0] ? hashone[c[0]][n] : t[0]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    precalc(n);
    string A, B, C;
    cin >> A >> B >> C;
    //cout << combine(B, C) << '\n';
    unordered_set<ll> hashes;
    hashes.insert(calcHash(A));
    hashes.insert(calcHash(B));
    hashes.insert(calcHash(C));
    hashes.insert(calcHash(combine(A, B)));
    hashes.insert(calcHash(combine(A, C)));
    hashes.insert(calcHash(combine(B, C)));
    hashes.insert(calcHash(combine(combine(A, B), C)));
    hashes.insert(calcHash(combine(combine(A, C), B)));
    hashes.insert(calcHash(combine(combine(B, C), A)));
    int q;
    cin >> q;
    string s;
    cin >> s;
    if (hashes.count(calcHash(s))) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    t.resize(4 * n);
    c.resize(4 * n);
    has.resize(4 * n);
    build(0, 0, n, s);
    for (int i = 0; i < q; ++i) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        l--, r--;
        update(0, 0, n, l, r + 1, toi(c));
        if (hashes.count(query(n))) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

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