Submission #580443

#	Time	Username	Problem	Language	Result	Execution time	Memory
580443		colossal_pepe	Crossing (JOI21_crossing)	C++17	26 / 100	543 ms	30476 KiB

Main

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct Node {
    int cnt_s[3], cnt_t[3], lazy;
    bool match;
    Node() {
        cnt_s[0] = cnt_s[1] = cnt_s[2] = 0;
        cnt_t[0] = cnt_t[1] = cnt_t[2] = 0;
        lazy = -1;
    }
};

int n, q;
string s, t;
vector<Node> sgt;

int id(char c) {
    if (c == 'J') return 0;
    else if (c == 'O') return 1;
    else return 2;
}

void init(int u, int l, int r) {
    if (l == r) {
        sgt[u].cnt_s[id(s[l])]++;
        sgt[u].cnt_t[id(t[l])]++;
        sgt[u].match = (s[l] == t[l]);
    } else {
        int mid = (l + r) / 2;
        init(2 * u, l, mid);
        init(2 * u + 1, mid + 1, r);
        for (int i = 0; i < 3; i++) {
            sgt[u].cnt_s[i] = sgt[2 * u].cnt_s[i] + sgt[2 * u + 1].cnt_s[i];
            sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
        }
        sgt[u].match = (sgt[2 * u].match & sgt[2 * u + 1].match);
    }
}

void update(int u, int l, int r, int L, int R, int x) {
    if (r < L or R < l) return;
    else if (L <= l and r <= R) {
        memset(sgt[u].cnt_t, 0, sizeof(sgt[u].cnt_t));
        sgt[u].cnt_t[x] = r - l + 1;
        sgt[u].lazy = x;
        sgt[u].match = (sgt[u].cnt_s[x] == sgt[u].cnt_t[x]);
    } else {
        int mid = (l + r) / 2;
        if (sgt[u].lazy != -1) {
            memset(sgt[2 * u].cnt_t, 0, sizeof(sgt[2 * u].cnt_t));
            memset(sgt[2 * u + 1].cnt_t, 0, sizeof(sgt[2 * u + 1].cnt_t));
            sgt[2 * u].cnt_t[sgt[u].lazy] = mid - l + 1;
            sgt[2 * u].match = (sgt[2 * u].cnt_s[sgt[u].lazy] == sgt[2 * u].cnt_t[sgt[u].lazy]);
            sgt[2 * u + 1].cnt_t[sgt[u].lazy] = r - mid;
            sgt[2 * u + 1].match = (sgt[2 * u + 1].cnt_s[sgt[u].lazy] == sgt[2 * u + 1].cnt_t[sgt[u].lazy]);
            sgt[2 * u].lazy = sgt[2 * u + 1].lazy = sgt[u].lazy;
            sgt[u].lazy = -1;
        }
        update(2 * u, l, mid, L, R, x);
        update(2 * u + 1, mid + 1, r, L, R, x);
        for (int i = 0; i < 3; i++) {
            sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
        }
        sgt[u].match = (sgt[2 * u].match & sgt[2 * u + 1].match);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s >> s >> s >> q >> t;
    sgt.resize(4 * n, Node());
    init(1, 0, n - 1);
    cout << (sgt[1].match ? "Yes" : "No") << endl;
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        update(1, 0, n - 1, l - 1, r - 1, id(c));
        cout << (sgt[1].match ? "Yes" : "No") << endl;
    }
    return 0;
}

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