Submission #492042

#	Time	Username	Problem	Language	Result	Execution time	Memory
492042		alextodoran	Crossing (JOI21_crossing)	C++17	100 / 100	460 ms	42296 KiB

Main

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = (int) 2e5;

int N;

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

void read (int V[]) {
    string str;
    cin >> str;
    for (int i = 0; i < N; i++) {
        V[i] = convert(str[i]);
    }
}

int Sinit[3][N_MAX];
int S[9][N_MAX];

int Q;

int T[N_MAX];

struct SGTNode {
    int fullS[9];
    int fullT;
    bool match[9];
};

SGTNode operator + (const SGTNode &u, const SGTNode &v) {
    SGTNode w;
    for (int k = 0; k < 9; k++) {
        w.fullS[k] = (u.fullS[k] == v.fullS[k] ? u.fullS[k] : -1);
        w.match[k] = (u.match[k] & v.match[k]);
    }
    w.fullT = -1;
    return w;
}

void setT (SGTNode &u, const int &value) {
    u.fullT = value;
    for (int k = 0; k < 9; k++) {
        u.match[k] = (u.fullS[k] == u.fullT);
    }
}

SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        for (int k = 0; k < 9; k++) {
            SGT[node].fullS[k] = S[k][l];
        }
        setT(SGT[node], T[l]);
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build () {
    build(1, 0, N - 1);
}

void split (int node) {
    if (SGT[node].fullT == -1) {
        return;
    }

    int lSon = node * 2, rSon = node * 2 + 1;
    setT(SGT[lSon], SGT[node].fullT);
    setT(SGT[rSon], SGT[node].fullT);
    SGT[node].fullT = -1;
}

void update (int node, int l, int r, int ul, int ur, int uval) {
    if (ul <= l && r <= ur) {
        setT(SGT[node], uval);
        return;
    }

    split(node);
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ul <= mid) {
        update(lSon, l, mid, ul, ur, uval);
    }
    if (mid + 1 <= ur) {
        update(rSon, mid + 1, r, ul, ur, uval);
    }

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int ul, int ur, int uval) {
    update(1, 0, N - 1, ul, ur, uval);
}

bool query () {
    for (int k = 0; k < 9; k++) {
        if (SGT[1].match[k] == true) {
            return true;
        }
    }
    return false;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int k = 0; k < 3; k++) {
        read(Sinit[k]);
    }

    {
        int curr = 0;
        int coef[3];
        for (coef[0] = 0; coef[0] < 3; coef[0]++) {
            for (coef[1] = 0; coef[1] < 3; coef[1]++) {
                for (coef[2] = 0; coef[2] < 3; coef[2]++) {
                    if ((coef[0] + coef[1] + coef[2]) % 3 == 1) {
                        for (int i = 0; i < N; i++) {
                            for (int k = 0; k < 3; k++) {
                                S[curr][i] += Sinit[k][i] * coef[k];
                            }
                            S[curr][i] %= 3;
                        }
                        curr++;
                    }
                }
            }
        }
    }

    cin >> Q;
    read(T);

    build();
    cout << (query() == true ? "Yes" : "No") << "\n";

    while (Q--) {
        int ul, ur;
        char c;
        cin >> ul >> ur >> c; ul--; ur--;
        int uval = convert(c);
        update(ul, ur, uval);
        cout << (query() == true ? "Yes" : "No") << "\n";
    }

    return 0;
}

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