Submission #1221816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221816		Trustfulcomic	Crossing (JOI21_crossing)	C++20	0 / 100	114 ms	1012 KiB

Main

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

struct node {
    char val = 'Z';
    char lazy = 'X';

    char match = 'Z';
    bool good = true;
};

vector<node> intervalac;

char get_val(int cur) {
    if (intervalac[cur].lazy != 'X') {
        return intervalac[cur].lazy;
    } else {
        return intervalac[cur].val;
    }
}

void res_laz(int cur) {
    if (intervalac[cur].lazy != 'X') {
        intervalac[cur].val = intervalac[cur].lazy;
        if (cur < intervalac.size()/2) {
            intervalac[2*cur].lazy = intervalac[cur].lazy;
            intervalac[2*cur+1].lazy = intervalac[cur].lazy; 
        }
        intervalac[cur].lazy = 'X';
    }

    if (intervalac[cur].match != 'Y'){
        if (intervalac[cur].val == intervalac[cur].match) {
            intervalac[cur].good = true;
        } else {
            intervalac[cur].good = false;
        }
    }
}

void resolve(int cur) {
    if (intervalac[cur].lazy != 'X') {
        intervalac[cur].val = intervalac[cur].lazy;
        if (cur < intervalac.size()/2) {
            intervalac[2*cur].lazy = intervalac[cur].lazy;
            intervalac[2*cur+1].lazy = intervalac[cur].lazy; 
        }
        intervalac[cur].lazy = 'X';
    } else {
        if (cur < intervalac.size()/2) {
            if (get_val(2*cur) == get_val(2*cur+1)) {
                intervalac[cur].val = get_val(2*cur);
            } else {
                intervalac[cur].val = 'X';
            }
        }
    }

    if (cur < intervalac.size()/2) {
        res_laz(2*cur);
        res_laz(2*cur+1);
    }

    if (intervalac[cur].match == 'Y') {
        if (intervalac[2*cur].good && intervalac[2*cur+1].good) {
            intervalac[cur].good = true;
        } else {
            intervalac[cur].good = false;
        }
    } else {
        if (intervalac[cur].match == intervalac[cur].val) {
            intervalac[cur].good = true;
        } else {
            intervalac[cur].good = false;
        }
    }
}

void update(int cur, int a, int b, int l, int r, char val) {
    resolve(cur);

    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);
    } else if (a >= (l+r)/2) {
        update(2*cur+1, a, b, (l+r)/2, r, val);
    } else {
        update(2*cur, a, (l+r)/2, l, (l+r)/2, val);
        update(2*cur+1, (l+r)/2, b, (l+r)/2, r, val);
    }

    resolve(cur);
}

int main() {
    int n; cin >> n;
    vector<string> strs(3);
    for (string &str : strs) cin >> str;

    int i_size = 1;
    while (i_size < n) i_size *= 2;
    i_size *= 2;
    intervalac.resize(i_size);
    for (int i = 0; i<strs[0].size(); i++) {
        intervalac[i + intervalac.size()/2].match = strs[0][i];
    }
    for (int i = 0; i < intervalac.size(); i++) {
        intervalac[i].good = true;
    }
    for (int i = intervalac.size()/2-1; i>0; i--) {
        if (intervalac[2*i].match == intervalac[2*i+1].match) {
            intervalac[i].match = intervalac[2*i].match;
        } else {
            intervalac[i].match = 'Y';
        }
    }

    int q; cin >> q;
    string start_str; cin >> start_str;
    for (int i = 0; i<n; i++) {
        update(1, i, i+1, 0, intervalac.size()/2, start_str[i]);
    }
    vector<bool> res(q+1, false);
    if (intervalac[1].good) res[0] = true;
    for (int i = 1; i<q+1; i++) {
        int a,b; cin >> a >> b; a--;
        char v; cin >> v;
        update(1, a, b, 0, intervalac.size()/2, v);
        res[i] = intervalac[1].good;
    }

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

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