Submission #1171223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171223		KhoaDuy	Curtains (NOI23_curtains)	C++20	100 / 100	458 ms	59728 KiB

curtains

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
struct T{
    int l=-1,r=-1;
};
T Tid;
T TT(T &le,T &ri){
    T pa;
    if(le.l==-1){
        pa=ri;
        return pa;
    }
    if(ri.l==-1){
        pa=le;
        return pa;
    }
    if(le.r+1>=ri.l){
        pa.r=max(le.r,ri.r);
        pa.l=le.l;
    }
    else{
        pa=ri;
    }
    return pa;
}
struct segtree{
    vector<T> seg;
    int n,lg;
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(int siz){
        n=1;
        while(n<siz){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
    }
    void update(int l,int r){
        l+=n;
        seg[l].l=l-n,seg[l].r=max(seg[l].r,r);
        for(int i=1;i<=lg;i++){
            refresh(l>>i);
        }
    }
    T query(int l,int r){
        l+=n,r+=n;
        T le=Tid,ri=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                le=TT(le,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                ri=TT(seg[r],ri);
            }
        }
        return TT(le,ri);
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,q;
    cin >> n >> m >> q;
    segtree seg;
    seg.build(n+1);
    bool ans[q];
    vector<vector<pair<int,int>>> que(n+1);
    vector<vector<int>> group(n+1);
    while(m--){
        int l,r;
        cin >> l >> r;
        group[r].push_back(l);
    }
    for(int i=0;i<q;i++){
        int s,e;
        cin >> s >> e;
        que[e].push_back({s,i});
    }
    for(int r=1;r<=n;r++){
        for(int l:group[r]){
            seg.update(l,r);
        }
        for(pair<int,int> &x:que[r]){
            int l=x.first,idx=x.second;
            T curr=seg.query(l,r+1);
            if(curr.l==l&&curr.r==r){
                ans[idx]=true;
            }
            else{
                ans[idx]=false;
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
}

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