Submission #1259774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259774		phtung	Curtains (NOI23_curtains)	C++20	0 / 100	0 ms	324 KiB

curtains

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

struct Node {
    int mx1, mx2, cnt, tag; // for range chmin + range max query
    Node(int v = (int)1e9) : mx1(v), mx2(-1), cnt(1), tag((int)1e9) {}
};
struct SegTree {
    int n;
    vector<Node> st;
    SegTree(int _n=0): n(_n), st(4*_n+5) {}
    static Node merge(const Node& L, const Node& R){
        Node res;
        if (L.mx1 == R.mx1){
            res.mx1 = L.mx1;
            res.cnt = L.cnt + R.cnt;
            res.mx2 = max(L.mx2, R.mx2);
        } else if (L.mx1 > R.mx1){
            res.mx1 = L.mx1;
            res.cnt = L.cnt;
            res.mx2 = max(L.mx2, R.mx1);
        } else {
            res.mx1 = R.mx1;
            res.cnt = R.cnt;
            res.mx2 = max(L.mx1, R.mx2);
        }
        res.tag = (int)1e9;
        return res;
    }
    void build(int p, int l, int r){
        st[p].tag = (int)1e9;
        if (l == r){ st[p] = Node((int)1e9); return; }
        int m=(l+r)>>1;
        build(p<<1,l,m); build(p<<1|1,m+1,r);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    void apply_chmin(int p, int x){
        if (x >= st[p].mx1) return;
        st[p].mx1 = x;
        st[p].tag = min(st[p].tag, x);
    }
    void push(int p){
        if (st[p].tag == (int)1e9) return;
        int x = st[p].tag;
        // it's safe since x > child.mx2 due to beats invariant
        apply_chmin(p<<1, x);
        apply_chmin(p<<1|1, x);
        st[p].tag = (int)1e9;
    }
    void range_chmin(int p, int l, int r, int ql, int qr, int x){
        if (ql>r || qr<l || x >= st[p].mx1) return;
        if (ql<=l && r<=qr && x > st[p].mx2){
            apply_chmin(p, x);
            return;
        }
        push(p);
        int m=(l+r)>>1;
        range_chmin(p<<1,l,m,ql,qr,x);
        range_chmin(p<<1|1,m+1,r,ql,qr,x);
        st[p] = merge(st[p<<1], st[p<<1|1]);
    }
    int range_max(int p, int l, int r, int ql, int qr){
        if (ql>r || qr<l) return -1;
        if (ql<=l && r<=qr) return st[p].mx1;
        push(p);
        int m=(l+r)>>1;
        return max(range_max(p<<1,l,m,ql,qr), range_max(p<<1|1,m+1,r,ql,qr));
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q; 
    if(!(cin>>n>>m>>q)) return 0;

    vector<vector<int>> addAtL(n+2);
    vector<char> hasPoint(n+2, 0);

    for(int i=0;i<m;i++){
        int l,r; cin>>l>>r;
        if(l==r) hasPoint[l]=1;
        if(l<r) addAtL[l].push_back(r); // affects gaps [l, r-1]
    }

    struct Q {int s,e,id;};
    vector<vector<Q>> qsAtS(n+2);
    vector<string> ans(q);
    for(int i=0;i<q;i++){
        int s,e; cin>>s>>e;
        if(s==e){
            ans[i] = (hasPoint[s] ? "YES" : "NO");
        } else {
            qsAtS[s].push_back({s,e,i});
        }
    }

    if (n>=2){
        SegTree st(n-1);
        st.build(1,1,n-1);

        for(int s=n; s>=1; --s){
            // add intervals with left = s
            for(int r: addAtL[s]){
                // update gaps [s, r-1] with chmin by r
                st.range_chmin(1,1,n-1,s,r-1,r);
            }
            // answer queries starting at s
            for(auto &qq: qsAtS[s]){
                int e = qq.e;
                int mx = st.range_max(1,1,n-1,s,e-1);
                ans[qq.id] = (mx <= e ? "YES" : "NO");
            }
        }
    } else {
        // n == 1: only s==e queries are possible; already handled.
        // All s<e are impossible, but there can't be as e<=n.
    }

    for(auto &x: ans) if(!x.empty()) cout<<x<<"\n";
    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20