Submission #804769

#	Time	Username	Problem	Language	Result	Execution time	Memory
804769		myst6	Crossing (JOI21_crossing)	C++14	49 / 100	7049 ms	63312 KiB

Main

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

struct segtree2 {
    vector<int> nodes, upd;
    segtree2(int sz) {
        nodes.resize(sz*4);
        upd.resize(sz*4,-1);
    }
    segtree2() : segtree2(0) {}
    int lc(int x) { return x << 1; }
    int rc(int x) { return lc(x) | 1; }
    void pushdown(int x) {
        if (upd[x] != -1) {
            nodes[x] = upd[x];
            if (lc(x) < nodes.size()) nodes[lc(x)] = upd[x];
            if (rc(x) < nodes.size()) nodes[rc(x)] = upd[x];
            upd[x] = -1;
        }
    }
    void update(int l, int r, int x, int xl, int xr, bool b) {
        if (l > r) return;
        pushdown(x);
        if (l == xl && r == xr) {
            upd[x] = b;
        } else {
            int xm = (xl + xr) >> 1;
            update(l, min(r,xm), lc(x), xl, xm, b);
            update(max(xm+1,l), r, rc(x), xm+1, xr, b);
            pushdown(lc(x));
            pushdown(rc(x));
            nodes[x] = nodes[lc(x)] || nodes[rc(x)];
        }
    }
    bool query() {
        pushdown(1);
        return nodes[1];
    }
};

struct intervals {
    segtree2 tree;
    int sz;
    intervals(int sz) {
        this->sz = sz;
        tree = segtree2(sz);
    }
    intervals() : intervals(0) {}
    void add(int l, int r) {
        tree.update(l, r, 1, 0, sz-1, 1);
    }
    void remove(int l, int r) {
        tree.update(l, r, 1, 0, sz-1, 0);
    }
    bool empty() {
        return !tree.query();
    }
};

struct segtree {
    vector<char> orig;
    vector<char> upd;
    intervals wrong;
    segtree(string s) {
        int sz = (int)s.size();
        orig.resize(sz*4,0);
        upd.resize(sz*4,0);
        build(s,1,0,sz-1);
        wrong = intervals(sz);
    }
    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 check(int x, int xl, int xr) {
        if (upd[x] != orig[x]) {
            wrong.add(xl, xr);
        } else {
            wrong.remove(xl, xr);
        }
    }
    void pushdown(int x, int xl, int xr) {
        if (xl == xr) return;
        if (upd[x] == '0') return;
        wrong.remove(xl, xr);
        int xm = (xl + xr) >> 1;
        if (lc(x) < upd.size()) {
            upd[lc(x)] = upd[x];
            check(lc(x), xl, xm);
        }
        if (rc(x) < upd.size()) {
            upd[rc(x)] = upd[x];
            check(rc(x), xm+1, xr);
        }
        upd[x] = '0';
    }
    void update(int l, int r, int x, int xl, int xr, char c) {
        if (l > r) return;
        assert(x != 0);
        pushdown(x, xl, xr);
        if (l == xl && r == xr) {
            upd[x] = c;
            check(x, xl, xr);
        } else {
            int xm = (xl + xr) >> 1;
            update(l, min(xm,r), lc(x), xl, xm, c);
            update(max(xm+1,l), r, rc(x), xm+1, xr, c);
        }
    }
};

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;

    set<string> V;
    V.insert(a);
    V.insert(b);
    V.insert(c);
    bool upd = true;
    while (upd) {
        upd = false;
        for (auto it1=V.begin(); it1!=V.end(); it1++) {
            for (auto it2=V.begin(); it2!=V.end(); it2++) {
                if (it1 == it2) continue;
                string x = cross(*it1, *it2);
                if (!V.count(x)) {
                    V.insert(x);
                    upd = true;
                }
            }
        }
    }

    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.wrong.empty()) {
                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 segtree2::pushdown(int)':
Main.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if (lc(x) < nodes.size()) nodes[lc(x)] = upd[x];
      |                 ~~~~~~^~~~~~~~~~~~~~
Main.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             if (rc(x) < nodes.size()) nodes[rc(x)] = upd[x];
      |                 ~~~~~~^~~~~~~~~~~~~~
Main.cpp: In member function 'void segtree::pushdown(int, int, int)':
Main.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (lc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~
Main.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         if (rc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~

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