Submission #804690

#	Time	Username	Problem	Language	Result	Execution time	Memory
804690		myst6	Crossing (JOI21_crossing)	C++14	26 / 100	6235 ms	9816 KiB

Main

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

struct intervals {
    set<pair<int,int>> LR;
    intervals() {}
    void _add(int l, int r) {
        if (l > r) return;
        else LR.insert({l, r});
    }
    void add(int l, int r) {
        remove(l, r);
        _add(l, r);
    }
    void remove(int l, int r) {
        auto it = LR.lower_bound({l,0});
        if (it != LR.begin()) {
            --it;
            int l2 = it->first;
            int r2 = it->second;
            LR.erase(it);
            _add(l2,min(l-1,r2));
            it = LR.lower_bound({l,0});
        }
        while (it != LR.end() && it->first <= r) {
            int l2 = it->first;
            int r2 = it->second;
            LR.erase(it);
            _add(max(r+1,l2),r2);
            it = LR.lower_bound({l,0});
        }
    }
    void print() {
        for (pair<int,int> seg : LR) {
            cout << "[" << seg.first << "," << seg.second << "] U ";
        }
        cout << "[] \n";
    }
    bool empty() {
        return LR.empty();
    }
};

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);
    }
    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;
                }
            }
        }
    }

    if (V.size() == 1) {
        segtree tree(a);
        int q;
        cin >> q;
        string t;
        cin >> t;
        for (int i=0; i<(int)t.size(); i++) {
            tree.update(i,i,1,0,n-1,t[i]);
        }
        cout << ( tree.wrong.empty() ? "Yes" : "No" ) << "\n"; 
        // tree.wrong.print();
        for (int i=0; i<q; i++) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            char c;
            cin >> c;
            tree.update(l,r,1,0,n-1,c);
            cout << ( tree.wrong.empty() ? "Yes" : "No" ) << "\n"; 
            // tree.wrong.print();
        }
    } else { // F

    }
    return 0;
}

Compilation message (stderr)

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

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