Submission #1223693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223693		adam17	Crossing (JOI21_crossing)	C++20	0 / 100	432 ms	3020 KiB

Main

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

struct zmena{
    int l;
    int r;
    short x;
};

int N, Q, hh, H;
vector<vector<short>> mozne;
vector<short> T;
vector<bool> OK;
vector<bool> OK_znaky;
string nacteno;
vector<vector<int>> pod;
vector<int> konce;
vector<vector<int>> I;
vector<int> L;
// vector<int> R;
int NN;
vector<zmena> zmeny;

short preved(char x) {
    return ((x == 'O') ? 0 : ((x == 'I') ? 1 : 2));
}

void refresh() {
    // cout << "refreshing\n";
    hh = 1;
    H = 1;
    while (hh <= NN) {
        H++;
        hh *= 2;
    }
    pod.resize(H);
    for (int h = 0; h < H; h++) {
        pod[h].resize(N / hh + 1);
        for (int i = 0; i < N / hh + 1; i++){
            pod[h][i] = 0;
        }
        hh *= 2;
    }
    konce.resize(NN);
    for (int i = 0; i < NN; i++) {
        konce[i] = -1;
    }
    // cout << "refreshed\n";
}

void pridej(int l, int r) { // Když je zajištěno, že nekoliduje
    konce[l] = r;
    pod[0][l] = 1;
    hh = 2;
    for (int h = 1; h < H; h++) {
        pod[h][l / hh] = pod[h - 1][l / hh * 2] + pod[h - 1][l / hh * 2 + 1];
        hh *= 2;
    }
}

void oddelej(int l) { // Když je zajištěno, že nekoliduje
    konce[l] = -1;
    pod[0][l] = 0;
    hh = 2;
    for (int h = 1; h < H; h++) {
        pod[h][l / hh] = pod[h - 1][l / hh * 2] + pod[h - 1][l / hh * 2 + 1];
        hh *= 2;
    }
}

int left(int i) {
    int h = 1;
    bool zprava = i % 2;
    i /= 2;
    while (!(zprava && (pod[h - 1][2 * i] != 0))) {
        zprava = i % 2;
        h++;
        if (h == H) {
            return -1;
        }
        i /= 2;
    }
    h--;
    i = 2 * i;
    while (h > 0) {
        if (pod[h - 1][2 * i + 1] != 0) {
            i = 2 * i + 1;
        } else {
            i *= 2;
        }
        h--;
    }
    return i;
}

int right(int i) {
    int h = 1;
    bool zleva = 1 - (i % 2);
    i = 2 * i + 1;
    while (!(zleva && (pod[h - 1][2 * i + 1] != 0))) {
        zleva = 1 - (i % 2);
        h++;
        if (h == H) {
            return -1;
        }
        i /= 2;
    }
    h--;
    i = 2 * i + 1;
    while (h > 0) {
        if (pod[h - 1][2 * i] != 0) {
            i *= 2;
        } else {
            i = 2 * i + 1;
        }
        h--;
    }
    return i;
}

int prochazi(int i) {
    int hranice = left(i);
    if (hranice == -1) {
        return -1;
    } else if (konce[hranice] < i) {
        return -1;
    } else {
        return hranice;
    }
}

void add(int l, int r, bool x) {
    // cout << "add(" << l << ", " << r << ", " << x << ");\n";
    // cout << "adding " << l << "-" << r << (x ? " (zapnutí)" : " (vypnutí)") << endl;
    if (l != r) {
        // int leva_hranice = left(l);
        // int leva = ((leva_hranice != -1) ? ((konce[leva_hranice] >= l) ? leva_hranice : -1) : -1);
        // int index = ((leva != -1) ? leva : right(l));
        // while (index <= r) {
            
        // }
        int index = ((pod[0][l] == 0) ? right(l) : l);
        while (index != -1) {
            if (index >= r) {
                goto break0;
            }
            int zrusit = index;
            index = right(index);
            oddelej(zrusit);
        }
        break0:;

        if (x) {
            int proch = prochazi(r);
            int konec = r;
            if (proch != -1) {
                konec = konce[proch];
                oddelej(proch);
            }
            proch = prochazi(l);
            if (proch != -1) {
                konce[proch] = konec;
            } else {
                pridej(l, konec);
            }
        } else {
            int proch = prochazi(l);
            if (proch != -1) {
                konce[proch] = l;
            }
            proch = prochazi(r);
            if (proch > r) {
                pridej(r, konce[proch]);
                oddelej(proch);
            }
        }
    } else {
        // cout << "adding l = r" << (x ? " (zapnutí)" : " (vypnutí)") << endl;
    }
}

bool decide() {
    if (NN != 0) {
        // cout << "decided konce[0] = " << konce[0] << ", NN = " << NN << endl;
        return (konce[0] == NN) || (NN == 0);
    } else {
        // cout << "deciding for NN = 0\n";
        return true;
    }
}


int main() {
    // scanf("%i", &N);
    cin >> N;
    mozne.resize(9);
    for (int i = 0; i < 9; i++) {
        mozne[i].resize(N);
        if (i < 3) {
            // scanf("%s", &(nacteno[0]));
            cin >> nacteno;
        }
        for (int j = 0; j < N; j++) {
            if (i < 3) {
                mozne[i][j] = preved(nacteno[j]);
            } else if (i < 6) {
                mozne[i][j] = (12 - mozne[(i + 1) % 3][j] - mozne[(i + 2) % 3][j]) % 3;
            } else {
                mozne[i][j] = (3 + mozne[(i + 1) % 3][j] + mozne[(i + 2) % 3][j] - mozne[i % 3][j]) % 3;
            }
            // cout << "OIJ"[mozne[i][j]];
        }
        // cout << endl;
    }

    // scanf("%i", &Q);
    cin >> Q >> nacteno;
    // scanf("%s", &(nacteno[0]));
    T.resize(N);
    for (int i = 0; i < N; i++) {
        T[i] = preved(nacteno[i]);
    }
    
    zmeny.resize(Q);
    for (int i = 0; i < Q; i++) {
        // scanf("%i %i %s", &(zmeny[i].l), &(zmeny[i].r), &(nacteno[0]));
        char xx;
        cin >> zmeny[i].l >> zmeny[i].r >> xx;
        zmeny[i].l--;
        zmeny[i].x = preved(xx);
        // cout << "zmeny[" << i << "] = {" << zmeny[i].l << ", " << zmeny[i].r << ", " << zmeny[i].x << ")" << endl;
    }


    // for (int q = 0; q <= Q; q++) {
    //     bool ok = false;
    //     for (int i = 0; i < 9; i++) {
    //         bool ok_zde = true;
    //         for (int j = 0; j < N; j++) {
    //             if (mozne[i][j] != T[j]) {
    //                 ok_zde = false;
    //             }
    //         }
    //         if (ok_zde) {
    //             ok = true;
    //         }
    //     }
        

    //     cout << (ok ? "Yes" : "No") << endl;
    //     // nacteno = (ok ? "Yes" : "No");
    //     // printf("%s\n", &(nacteno[0]));


    //     if (q != Q) {
    //         int l, r; char xx;
    //         // scanf("%i %i %s", &l, &r, &(nacteno[0])); l--;
    //         cin >> l >> r >> xx; l--;
    //         short x = preved(xx);
    //         for (int j = l; j < r; j++) {
    //             T[j] = x;
    //         }
    //     }
    // }

    OK.resize(Q + 1);
    for (int i = 0; i <= Q; i++) OK[i] = false;
    OK_znaky.resize(Q + 1);

    I.resize(3);
    NN;
    L.resize(N + 1);
    // R.resize(N);

    for (int ii = 0; ii < 9; ii++) {
    // for (int ii = 2; ii == 2; ii = 2147483647) {
        for (int i = 0; i < 3; i++) {
            I[i].resize(0);
        }
        for (int i = 0; i < N; i++) {
            I[mozne[ii][i]].push_back(i);
        }
        for (int i = 0; i <= Q; i++) {
            OK_znaky[i] = true;
        }
        for (int x = 0; x < 3; x++) {
            // cout << "Testuji shody pro " << ii << ". variantu crossingu z pohledu znaku " << x << " (0=O, 1=I, 2=J)" << endl;
            NN = I[x].size();
            // R[0] = 0;
            // for (int j = 1; j < N; j++) {
            //     R[j] = ((T[j] == i) ? (R[j - 1] + 1) : (R[j - 1]));
            // }
            // L[N - 1] = NN;
            // cout << "L[" << N - 1 << "] = " << L[N - 1] << endl;
            // for (int j = N - 2; j >= 0; j--) {
            //     L[j] = ((mozne[ii][j + 1] == x) ? (L[j + 1] - 1) : (L[j + 1]));
            //     cout << "L[" << j << "] = " << L[j] << endl;
            // }
            
            L[0] = 0;
            for (int i = 1; i <= N; i++) {
                L[i] = L[i - 1] + ((mozne[ii][i - 1] == x) ? 1 : 0);
            }

            // cout << "NN = " << NN << ", L = ";
            // for (int i = 0; i < L.size(); i++) {
            //     cout << L[i] << ' ';
            // }
            // cout << endl;
            refresh();
            for (int i = 0; i < N; i++) {
                // cout << "inicializuji " << i << ". písmeno\n";
                if (T[i] == x) {
                    add(L[i], L[i + 1], true);
                }
            }

            if (!decide()) {
                OK_znaky[0] = false;
                // cout << "Verze 0 touto možností crossingu nejde\n";
            }
            for (int q = 0; q < Q; q++) {
                add(L[zmeny[q].l], L[zmeny[q].r], zmeny[q].x == x);
                if (!decide()) {
                    OK_znaky[q + 1] = false;
                    // cout << "Verze " << q + 1 << " touto možností crossingu nejde\n";
                }
            }
        }
        for (int i = 0; i <= Q; i++) {
            if (OK_znaky[i]) {
                OK[i] = true;
            }
        }
    }

    for (int i = 0; i <= Q; i++) {
        cout << (OK[i] ? "Yes" : "No") << endl;
    }
}

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