Submission #891256

#	Time	Username	Problem	Language	Result	Execution time	Memory
891256		lolicon	Crossing (JOI21_crossing)	C++14	100 / 100	2733 ms	295220 KiB

Main

#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
using namespace std;

const int maxn = 2e5 + 5;

void transform(int A[], int B[], int C[], int sz) {
    for(int i = 0; i < sz; ++i) {
        if(A[i] == B[i]) C[i] = A[i];
        else {
            C[i] = 3 - A[i] - B[i];
        }
    }
}

int get(char c) {
    if(c == 'J') return 0;
    if(c == 'O') return 1;
    if(c == 'I') return 2;
    return -1;
}

struct SGT {
    struct node {
        int cnt[3][3], tag;
    };
    vector<node> tr;
    SGT(int sz) : tr(sz << 2) {}
    void pull(int x) {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j)
                tr[x].cnt[i][j] = tr[(x << 1)].cnt[i][j] + tr[(x << 1) | 1].cnt[i][j];
        }
    }
    void print(int x) {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                printf("%d%c", tr[x].cnt[i][j], " \n"[j == 2]);
            }
        }
    } 
    void apply(int x, int color) {
        for(int i = 0; i < 3; ++i) {
            int sum = 0;
            for(int j = 0; j < 3; ++j) {
                sum += tr[x].cnt[i][j];
            }
            for(int j = 0; j < 3; ++j) {
                tr[x].cnt[i][j] = 0;
            }
            tr[x].cnt[i][color] = sum;
        }
    }
    void push(int x) {
        if(tr[x].tag != -1) {
            // apply
            apply(x << 1, tr[x].tag);
            apply((x << 1) | 1, tr[x].tag);
            
            // set tag
            tr[x << 1].tag = tr[x].tag;
            tr[(x << 1) | 1].tag = tr[x].tag;
            tr[x].tag = -1;
            // printf("pushed %d: \n", x << 1);
            // print(x << 1);
            // printf("pushed %d: \n", (x << 1) | 1);
            // print((x << 1) | 1);
        }
    }
    void build(int x, int L, int R, int ori[], int arr[]) {
        tr[x].tag = -1;
        if(L == R) {
            memset(tr[x].cnt, 0, sizeof(int)*9);
            tr[x].cnt[ori[L]][arr[L]]++;
            // printf("build %d: \n", x);
            // print(x);
            return;
        }
        int mid = (L + R) >> 1;
        build(x << 1, L, mid, ori, arr);
        build((x << 1) | 1, mid + 1, R, ori, arr);
        pull(x);
        // printf("build %d: \n", x);
        // print(x);
    }
    void upd(int x, int L, int R, int l, int r, int color) {
        // printf("upd [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
        if(l <= L && R <= r) {
            apply(x, color);
            tr[x].tag = color;
            // printf("upded [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
            // print(x);
            return;
        }
        push(x);
        int mid = (L + R) >> 1;
        if(l <= mid) upd(x << 1, L, mid, l, r, color);
        if(r > mid) upd((x << 1) | 1, mid + 1, R, l, r, color);
        pull(x);
        // printf("upded [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
        // print(x);
    }
    int ask() {
        int ret = 0;
        for(int i = 0; i < 3; ++i) {
            ret += tr[1].cnt[i][i];
        }
        return ret;
    }
};

int S[9][maxn], T[maxn];
vector<SGT> loli;
int n, q;

void upd(int l, int r, int c) {
    for(auto &it : loli) {
        it.upd(1, 0, n - 1, l, r, c);
    }
}

bool chk() {
    for(auto &it : loli) {
        if(it.ask() == n) return true;
    }
    return false;
}

void print(int A[]) {
    for(int i = 0; i < n; ++i) 
        printf("%d%c", A[i], " \n"[i == n - 1]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < 3; ++i) {
        string s; cin >> s;
        for(int j = 0; j < n; ++j) S[i][j] = get(s[j]);
    }
    cin >> q;
    string t; cin >> t;
    for(int i = 0; i < n; ++i) T[i] = get(t[i]);
    // print(T);
    // build tree
    transform(S[0], S[1], S[3], n);
    transform(S[0], S[2], S[4], n);
    transform(S[1], S[2], S[5], n);
    transform(S[3], S[4], S[6], n);
    transform(S[3], S[5], S[7], n);
    transform(S[4], S[5], S[8], n);
    for(int i = 0; i < 9; ++i) {
        // print(S[i]);
        loli.emplace_back(n);
        loli.back().build(1, 0, n - 1, S[i], T);
    }
    // solve
    cout << (chk() ? "Yes" : "No") << '\n';
    for(int i = 0; i < q; ++i) {
        int l, r, c; char _c;
        cin >> l >> r >> _c; c = get(_c); l--, r--;
        upd(l, r, c);
        cout << (chk() ? "Yes" : "No") << '\n';
    } 
    return 0;
}

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