Submission #804906

#	Time	Username	Problem	Language	Result	Execution time	Memory
804906		myst6	Crossing (JOI21_crossing)	C++14	100 / 100	2408 ms	23920 KiB

Main

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

struct segtree {
    vector<char> orig;
    vector<char> upd;
    vector<bool> match;
    segtree(string s) {
        int sz = (int)s.size();
        orig.resize(sz*4,0);
        upd.resize(sz*4,0);
        match.resize(sz*4,1);
        build(s,1,0,sz-1);
    }
    int lc(int x) { return x << 1; }
    int rc(int x) { return lc(x) | 1; }
    void build(string &s, int x, int xl, int xr) {
        if (xl == xr) orig[x] = upd[x] = s[xl];
        else {
            int xm = (xl + xr) >> 1;
            build(s,lc(x),xl,xm);
            build(s,rc(x),xm+1,xr);
            if (orig[lc(x)] == orig[rc(x)]) {
                orig[x] = upd[x] = orig[lc(x)];
            }
        }
    }
    void pushdown(int x) {
        if (upd[x] == '0') return;
        if (lc(x) < upd.size()) {
            upd[lc(x)] = upd[x];
            match[lc(x)] = upd[lc(x)] == orig[lc(x)];
        }
        if (rc(x) < upd.size()) {
            upd[rc(x)] = upd[x];
            match[rc(x)] = upd[rc(x)] == orig[rc(x)];
        }
        upd[x] = '0';
    }
    void update(int l, int r, int x, int xl, int xr, char c) {
        if (l > r) return;
        if (l == xl && r == xr) {
            upd[x] = c;
            match[x] = upd[x] == orig[x];
        } else {
            int xm = (xl + xr) >> 1;
            pushdown(x);
            update(l, min(xm,r), lc(x), xl, xm, c);
            update(max(xm+1,l), r, rc(x), xm+1, xr, c);
            pushdown(lc(x)); pushdown(rc(x));
            match[x] = match[lc(x)] && match[rc(x)];
        }
    }
    bool query() {
        return match[1];
    }
};

string cross(string a, string b) {
    string out = a;
    for (int i=0; i<(int)a.size(); i++) {
        if (a[i] != b[i]) {
            set<char> C = {'J', 'O', 'I'};
            C.erase(a[i]);
            C.erase(b[i]);
            out[i] = *C.begin();
        }
    }
    return out;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    string d = cross(a, b);
    string e = cross(b, c);
    string f = cross(c, a);
    string g = cross(d, e);
    string h = cross(e, f);
    string i = cross(f, d);

    set<string> V = {a,b,c,d,e,f,g,h,i};
    // cerr << V.size() << endl;

    vector<segtree> trees;
    for (const string &s : V) {
        trees.push_back(segtree(s));
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    for (int i=0; i<(int)t.size(); i++) {
        for (segtree &tree : trees) tree.update(i,i,1,0,n-1,t[i]);
    }
    auto output_ans = [&]() {
        bool ans = false;
        for (segtree &tree : trees) {
            if (tree.query()) {
                ans = true;
                break;
            }
        }
        cout << ( ans ? "Yes" : "No" ) << "\n";
    };
    output_ans();
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        char c;
        cin >> c;
        for (segtree &tree : trees) tree.update(l,r,1,0,n-1,c);
        output_ans();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::pushdown(int)':
Main.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (lc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (rc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~

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