Submission #804655

#	Time	Username	Problem	Language	Result	Execution time	Memory
804655		myst6	Crossing (JOI21_crossing)	C++14	26 / 100	6298 ms	13432 KiB

Main

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

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c) {
        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:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if (lc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~
Main.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if (rc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~

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