Submission #501655

#	Time	Username	Problem	Language	Result	Execution time	Memory
501655		tengiz05	Crossing (JOI21_crossing)	C++17	0 / 100	124 ms	1024 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

int pre[9][3][200005];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    auto in = [&]() {
        std::string a;
        std::cin >> a;
        std::vector<int> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = std::string("JOI").find(a[i]);
        }
        return b;
    };
    
    std::vector<int> a = in(), b = in(), c = in();
    
    auto merge = [&](std::vector<int> a, std::vector<int> b) {
        auto c = a;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                c[i] = 0 ^ 1 ^ 2 ^ a[i] ^ b[i];
            }
        }
        return c;
    };
    
    std::vector<std::vector<int>> s{a, b, c, merge(a, b), merge(a, c), merge(b, c), merge(merge(a, c), b), merge(merge(a, b), c), merge(merge(b, c), a)};
    
    int q;
    std::cin >> q;
    std::vector<int> t = in();
    
    for (int k = 0; k < 9; k++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                pre[k][i][j + 1] = pre[k][i][j] + (s[k][j] == i);
            }
        }
    }
    
    bool bad[9] {};
    for (int k = 0; k < 9; k++) {
        for (int i = 0; i < n; i++) {
            bad[k] += t[i] != s[k][i];
        }
    }
    std::set<std::pair<int, int>> p{{-1, -1}, {n, -1}};
    for (int i = 0; i < n; i++)
        p.emplace(i, t[i]);
    
    bool ok = false;
    for (int k = 0; k < 9; k++) {
        ok |= bad[k] == 0;
    }
    if (ok) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
    
    auto rem = [&](int l, int r, int c) {
        for (int k = 0; k < 9; k++) {
            bad[k] -= pre[k][c][r] - pre[k][c][l] != r - l;
        }
    };
    auto add = [&](int l, int r, int c) {
        for (int k = 0; k < 9; k++) {
            bad[k] += pre[k][c][r] - pre[k][c][l] != r - l;
        }
    };
    
    while (q--) {
        int l, r;
        char ch;
        std::cin >> l >> r >> ch;
        l--;
        
        int x = std::string("JOI").find(ch);
        
        auto it = p.lower_bound({l, -1});
        if (it->first > l) {
            int L = std::prev(it)->first;
            int R = it->first;
            int c = std::prev(it)->second;
            rem(L, R, c);
            add(L, l, c);
            add(l, R, c);
            p.emplace(l, c);
        }
        
        it = p.lower_bound({r, -1});
        if (std::prev(it)->first < r - 1) {
            int L = std::prev(it)->first;
            int R = it->first;
            int c = std::prev(it)->second;
            rem(L, R, c);
            add(L, r, c);
            add(r, R, c);
            p.emplace(r, c);
        }
        
        while (true) {
            it = p.lower_bound({l, -1});
            if (it->first < r) {
                rem(it->first, std::next(it)->first, it->second);
                p.erase(it);
            } else {
                break;
            }
        }
        
        add(l, r, x);
        p.emplace(l, x);
        
        bool ok = false;
        for (int k = 0; k < 9; k++) {
            ok |= bad[k] == 0;
        }
        if (ok) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }
    
    return 0;
}

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