Submission #530416

#	Time	Username	Problem	Language	Result	Execution time	Memory
530416		c28dnv9q3	Crossing (JOI21_crossing)	C++17	0 / 100	485 ms	1064 KiB

Main

#include <bits/stdc++.h>
#define lli long long int

using namespace std;

lli mod = 1000000009;

lli toInt(char c) {
    switch (c) {
        case 'J':
            return 0;
        case 'O':
            return 1;
        case 'I':
            return 2;
        default:
            return -1;
    }
}


int main() {
    vector<lli> seq[9];

    int n;
    cin >> n;

    vector<lli> pow3sum;
    pow3sum.push_back(0);
    for (int i = 0; i < n; ++i) pow3sum.push_back((pow3sum[i] * 3 + 1) % mod);

    string input[3];
    for (int i = 0; i < 3; ++i) cin >> input[i];

    vector<lli> in[3];
    for (int i = 0; i < 3; ++i) for (int j = 0; j < n; ++j) in[i].push_back(toInt(input[i][j]));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 9; ++j) {
            switch (j / 3) {
                case 0:
                    seq[j].push_back(in[j][i]);
                    break;
                case 1:
                    seq[j].push_back((- in[j % 3][i] - in[(j + 1) % 3][i] + 6) % 3);
                    break;
                case 2:
                    seq[j].push_back((in[j % 3][i] + in[(j + 1) % 3][i] - in[(j + 2) % 3][i] + 3) % 3);
                    break;
            }
        }
    }

    vector<lli> hashes;
    lli hash;
    for (int i = 0; i < 9; ++i) {
        hash = 0;
        for (int j = 0; j < n; ++j) {
            hash += (pow3sum[j + 1] - pow3sum[j] + mod) * seq[i][j];
            hash %= mod;
        }
        hashes.push_back(hash);
    }


    int m;
    cin >> m;

    set<vector<lli>> intervals;
    intervals.insert({-1, 0});
    intervals.insert({n, 0});
    string q;
    cin >> q;

    hash = 0;
    for (int i = 0; i < n; ++i) {
        intervals.insert({i, toInt(q[i])});
        hash += (pow3sum[i + 1] - pow3sum[i] + mod) * toInt(q[i]);
        hash %= mod;
    }

    vector<vector<lli>> erase;
    vector<vector<lli>> insert;

    char ch;
    lli s, e, c, d;

    cout << (std::find(hashes.begin(), hashes.end(), hash) != hashes.end() ? "Yes" : "No") << "\n";

    for (int i = 0; i < m; ++i) {
        cin >> s >> e >> ch;
        s--;
        e--;
        c = toInt(ch);

        erase = vector<vector<lli>>();
        insert = vector<vector<lli>>();
        for (auto index = --intervals.lower_bound({s - 1, 3}); (*index)[0] <= e; ++index) {
            d = (*index)[1];
            index++;
            hash = hash + (- pow3sum[min((*index)[0], e + 1)] + mod) * d;
            index--;
            hash = hash + (pow3sum[max((*index)[0], s)] + mod) * d;
            hash %= mod;
            index++;
            if ((*index)[0] > e + 1) insert.push_back({e + 1, d});
            index--;
            if ((*index)[0] >= s) erase.push_back(*index);
        }

        for (const auto& era: erase) intervals.erase(era);
        for (const auto& ins: insert) intervals.insert(ins);

        intervals.insert({s, c});
        hash += (pow3sum[e + 1] - pow3sum[s] + mod) * c;
        hash %= mod;

        cout << (std::find(hashes.begin(), hashes.end(), hash) != hashes.end() ? "Yes" : "No") << "\n";
    }
}

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