Submission #1221907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221907		Trustfulcomic	Crossing (JOI21_crossing)	C++20	49 / 100	7116 ms	413156 KiB

Main

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

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

    vector<bool> good = vector<bool>(9, true);
};

vector<vector<node>> int_ref(9);
int ref_num;

void res_laz(int cur, vector<node>& intervalac) {
    node& nd = intervalac[cur];
    vector<node> ref_nds;
    for (int j = 0; j<ref_num; j++){
        ref_nds.push_back(int_ref[j][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;

            for (int j = 0; j<ref_num; j++) {
                if (!ref_nds[j].same_ch) {
                    nd.good[j] = false;
                } else if (nd.value == ref_nds[j].value) {
                    nd.good[j] = true;
                } else {
                    nd.good[j] = false;
                }
            }
        }
    } else {
        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            nd.lazy = 'X';
        } 
        nd.same_ch = true;
        for (int j = 0; j<ref_num; j++) {
            if (!ref_nds[j].same_ch) {
                nd.good[j] = false;
            } else if (nd.value == ref_nds[j].value) {
                nd.good[j] = true;
            } else {
                nd.good[j] = false;
            }
        }
    }
}

void resolve(int cur, vector<node>& intervalac) {
    node& nd = intervalac[cur];
    vector<node> ref_nds;
    for (int j = 0; j<ref_num; j++){
        ref_nds.push_back(int_ref[j][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;

            for (int j = 0; j<ref_num; j++) {
                if (!ref_nds[j].same_ch) {
                    nd.good[j] = false;
                } else if (nd.value == ref_nds[j].value) {
                    nd.good[j] = true;
                } else {
                    nd.good[j] = 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;
                for (int j = 0; j<ref_num; j++) {
                    if (!ref_nds[j].same_ch) {
                        nd.good[j] = false;
                    } else if (nd.value == ref_nds[j].value) {
                        nd.good[j] = true;
                    } else {
                        nd.good[j] = false;
                    }
                }
            } else {
                nd.value = 'X';
                nd.same_ch = false;
                for (int j = 0; j<ref_num; j++) {
                    if (l_ch.good[j] && r_ch.good[j]) {
                        nd.good[j] = true;
                    } else {
                        nd.good[j] = false;
                    }
                }
            }
        }

    } else {
        if (nd.lazy != 'X') {
            nd.value = nd.lazy;
            nd.lazy = 'X';
        } 
        nd.same_ch = true;
        for (int j = 0; j<ref_num; j++) {
            if (!ref_nds[j].same_ch) {
                nd.good[j] = false;
            } else if (nd.value == ref_nds[j].value) {
                nd.good[j] = true;
            } else {
                nd.good[j] = 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);
}

string cross(string& a, string& b) {
    string r = "";
    for (int i = 0; i<a.size(); i++) {
        if (a[i] == b[i]) {
            r += a[i];
        } else {
            r += 73 + 74 + 79 - a[i] - b[i];
        }
    }
    return r;
}

vector<string> gen_all(vector<string> start) {
    set<string> st_set;
    for (string& s : start) {
        st_set.insert(s);
    }

    vector<string> s;
    for (const string& str : st_set) {
        s.push_back(str);
    }

    while (true) {
        set<string> new_s_set;
        vector<string> new_s;
        for (int i = 0; i<s.size(); i++) {
            for (int j = i+1; j<s.size(); j++) {
                string cr = cross(s[i], s[j]);
                if (new_s_set.find(cr) == new_s_set.end()) {
                    new_s.push_back(cr);
                    new_s_set.insert(cr);
                }
            }
        }

        for (string& str : s) {
            if (new_s_set.find(str) == new_s_set.end()) {
                new_s.push_back(str);
                new_s_set.insert(str);
            }
        }

        if (s.size() == new_s.size()) break;
        s = new_s;
    }
    return s;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;

    vector<string> refs = gen_all({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;

    ref_num = refs.size();

    vector<node> int_cur(i_size);
    for (int i = 0; i<ref_num; i++) {
        int_ref[i].resize(i_size);
    }


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

    vector<bool> res(q+1, false);
    for (int j = 0; j<ref_num; j++) {
        if (int_cur[1].good[j]) 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, i_size/2, v, int_cur);
        for (int j = 0; j<ref_num; j++) {
            if (int_cur[1].good[j]) res[i] = true;
        }
        
    }

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

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