Submission #530433

#	Time	Username	Problem	Language	Result	Execution time	Memory
530433		c28dnv9q3	Crossing (JOI21_crossing)	C++17	0 / 100	701 ms	1180 KiB

Main

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

using namespace std;

vector<lli> pow3sum;
lli mod = 1000000009;

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

vector<lli> toVec(string s) {
    vector<lli> v;
    for (char c: s) v.push_back(toInt(c));
    return v;
 }

lli toHash(vector<lli> v) {
    lli hash = 0;
    for (int i = 0; i < v.size(); ++i) {
        hash += (pow3sum[i + 1] - pow3sum[i] + mod) * v[i];
        hash %= mod;
    }
    return hash;
}

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

    int n;
    cin >> n;

    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) in[i] = toVec(input[i]);

    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;
    for (int i = 0; i < 9; ++i) {
        hashes.push_back(toHash(seq[i]));
    }

    int m;
    cin >> m;

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

    lli 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;

        fill(q.begin() + s, q.begin() + e + 1, ch);
        if (hash != toHash(toVec(q))) {
            return 1;
        }

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

Compilation message (stderr)

Main.cpp: In function 'long long int toHash(std::vector<long long int>)':
Main.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~

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