oj.uz

Submission #530412

# Submission time Handle Problem Language Result Execution time Memory
530412 2022-02-25T09:52:07 Z c28dnv9q3 Crossing (JOI21_crossing) C++17
0 / 100
 472 ms 2416 KB 
#include <bits/stdc++.h>
#define lli long long int

using namespace std;

lli mod = 1000000007;

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.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 836 KB Output is correct
2 Correct 472 ms 2416 KB Output is correct
3 Correct 444 ms 2288 KB Output is correct
4 Correct 432 ms 2268 KB Output is correct
5 Correct 430 ms 2284 KB Output is correct
6 Correct 442 ms 2348 KB Output is correct
7 Correct 442 ms 2380 KB Output is correct
8 Correct 456 ms 2344 KB Output is correct
9 Correct 447 ms 2368 KB Output is correct
10 Incorrect 445 ms 2372 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 836 KB Output is correct
2 Correct 472 ms 2416 KB Output is correct
3 Correct 444 ms 2288 KB Output is correct
4 Correct 432 ms 2268 KB Output is correct
5 Correct 430 ms 2284 KB Output is correct
6 Correct 442 ms 2348 KB Output is correct
7 Correct 442 ms 2380 KB Output is correct
8 Correct 456 ms 2344 KB Output is correct
9 Correct 447 ms 2368 KB Output is correct
10 Incorrect 445 ms 2372 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 836 KB Output is correct
2 Correct 472 ms 2416 KB Output is correct
3 Correct 444 ms 2288 KB Output is correct
4 Correct 432 ms 2268 KB Output is correct
5 Correct 430 ms 2284 KB Output is correct
6 Correct 442 ms 2348 KB Output is correct
7 Correct 442 ms 2380 KB Output is correct
8 Correct 456 ms 2344 KB Output is correct
9 Correct 447 ms 2368 KB Output is correct
10 Incorrect 445 ms 2372 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 836 KB Output is correct
2 Correct 472 ms 2416 KB Output is correct
3 Correct 444 ms 2288 KB Output is correct
4 Correct 432 ms 2268 KB Output is correct
5 Correct 430 ms 2284 KB Output is correct
6 Correct 442 ms 2348 KB Output is correct
7 Correct 442 ms 2380 KB Output is correct
8 Correct 456 ms 2344 KB Output is correct
9 Correct 447 ms 2368 KB Output is correct
10 Incorrect 445 ms 2372 KB Output isn't correct
11 Halted 0 ms 0 KB -