Submission #1221842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221842		Trustfulcomic	Crossing (JOI21_crossing)	C++20	26 / 100	481 ms	6212 KiB

Main

#include<bits/stdc++.h>
using namespace std;

struct node {
    char value = 'X';
    char lazy = 'X';
    bool same_ch = true;

    bool good = true;
};

vector<node> int_ref;

void res_laz(int cur, vector<node>& intervalac) {
    node& nd = intervalac[cur];
    node& nd_ref = int_ref[cur];
    if (cur < intervalac.size()/2) {
        node& l_ch = intervalac[2*cur];
        node& r_ch = intervalac[2*cur+1];

        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            l_ch.lazy = nd.lazy;
            r_ch.lazy = nd.lazy;
            nd.lazy = 'X';
            nd.same_ch = true;

            if (!nd_ref.same_ch) {
                nd.good = false;
            } else if (nd.value == nd_ref.value) {
                nd.good = true;
            } else {
                nd.good = false;
            }
        }
    } else {
        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            nd.lazy = 'X';
        } 
        nd.same_ch = true;
        if (!nd_ref.same_ch) {
            nd.good = false;
        } else if (nd.value == nd_ref.value) {
            nd.good = true;
        } else {
            nd.good = false;
        }
    }
}

void resolve(int cur, vector<node>& intervalac) {
    node& nd = intervalac[cur];
    node& nd_ref = int_ref[cur];
    if (cur < intervalac.size()/2) {
        node& l_ch = intervalac[2*cur];
        node& r_ch = intervalac[2*cur+1];

        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            l_ch.lazy = nd.lazy;
            r_ch.lazy = nd.lazy;
            nd.lazy = 'X';
            nd.same_ch = true;

            if (!nd_ref.same_ch) {
                nd.good = false;
            } else if (nd.value == nd_ref.value) {
                nd.good = true;
            } else {
                nd.good = false;
            }
        } else {
            res_laz(2*cur, intervalac);
            res_laz(2*cur+1, intervalac);
            if (l_ch.value == r_ch.value && l_ch.same_ch && r_ch.same_ch) {
                nd.value = l_ch.value;
                nd.same_ch = true;
                if (!nd_ref.same_ch) {
                    nd.good = false;
                } else if (nd.value == nd_ref.value) {
                    nd.good = true;
                } else {
                    nd.good = false;
                }
            } else {
                nd.value = 'X';
                nd.same_ch = false;
                if (l_ch.good && r_ch.good) {
                    nd.good = true;
                } else {
                    nd.good = false;
                }
            }
        }

    } else {
        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            nd.lazy = 'X';
        } 
        nd.same_ch = true;
        if (!nd_ref.same_ch) {
            nd.good = false;
        } else if (nd.value == nd_ref.value) {
            nd.good = true;
        } else {
            nd.good = false;
        }
    }
}

void update(int cur, int a, int b, int l, int r, char val, vector<node>& intervalac) {
    resolve(cur, intervalac);

    if (a == l && b == r) {
        intervalac[cur].lazy = val;
    } else if (b <= (l+r)/2) {
        update(2*cur, a, b, l, (l+r)/2, val, intervalac);
    } else if (a >= (l+r)/2) {
        update(2*cur+1, a, b, (l+r)/2, r, val, intervalac);
    } else {
        update(2*cur, a, (l+r)/2, l, (l+r)/2, val, intervalac);
        update(2*cur+1, (l+r)/2, b, (l+r)/2, r, val, intervalac);
    }

    resolve(cur, intervalac);
}

int main() {
    int n; cin >> n;
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;

    int q; cin >> q;
    string start_cur; cin >> start_cur;

    int i_size = 1;
    while (i_size < n) i_size *= 2;
    i_size *= 2;

    vector<node> int_cur(i_size);
    int_ref.resize(i_size);

    for (int i = 0; i < i_size/2; i++) {
        if (i < s1.size()) {
            update(1, i, i+1, 0, i_size/2, s1[i], int_ref);
            update(1, i, i+1, 0, i_size/2, start_cur[i], int_cur);
        } else {
            update(1, i, i+1, 0, i_size/2, 'Z', int_ref);
            update(1, i, i+1, 0, i_size/2, 'Z', int_cur);
        }
    }

    vector<bool> res(q+1);
    res[0] = int_cur[1].good;
    for (int i = 1; i<q+1; i++) {
        int a,b; cin >> a >> b; a--;
        char v; cin >> v;
        update(1, a, b, 0, i_size/2, v, int_cur);
        res[i] = int_cur[1].good;
    }

    for (bool b : res) {
        if (b) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

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