Submission #886087

#	Time	Username	Problem	Language	Result	Execution time	Memory
886087		vjudge1	Curtains (NOI23_curtains)	C++17	100 / 100	812 ms	93264 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;

struct segtree{
    int n, tl, tr;
    vector<int> t, st, marked;

    segtree(int _n){
        n = _n;
        st.resize(4*n, -1);
        t.resize(4*n,-1);
        marked.resize(4*n);
    }

    void push(int v, int l, int r){
        if(!marked[v]) return;

        if(l<r){
            if(st[v*2] < t[v]){
                st[v*2] = t[v];
                t[v*2] = t[v];
                marked[v*2] = 1;
            }
            if(st[v*2+1] < t[v]){
                st[v*2+1] = t[v];
                t[v*2+1] = t[v];
                marked[v*2+1] = 1;
            }   

            st[v] = merge(st[v*2], st[v*2+1]);
            
        }
        marked[v] = 0; t[v] = -1;
    }

    int merge(int x, int y){
        return min(x, y);
    }

    void update(int v, int l, int r, int val){
        push(v, l, r);

        if(l>tr || r< tl) return;

        if(r<=tr&&l>=tl){
            if(st[v] < val){
                t[v] = val;
                st[v] = t[v];
                marked[v] = 1;

            }
        }
        else{
            int mid = (l+r) / 2;
            update(v*2, l, mid, val); 
            update(v*2+1, mid+1, r, val);
            st[v] = merge(st[v*2], st[v*2+1]);
        }
    }

    void update(int l, int r, int val){
        tl = l; tr = r;
        update(1, 0, n-1, val);
    }

    int get(int v, int l, int r){
        push(v, l, r);

        if(l>tr || r<tl) return 1e9;
        else if(l>=tl&&r<=tr) return st[v];
        else{
            int mid = (l+r) / 2;
            return merge(get(v*2, l, mid), get(v*2+1, mid+1, r));
        }
    }

    int operator()(int l, int r){
         tl = l, tr = r;

        if(r<l) return 1e9;
        else return get(1, 0, n-1);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q; cin >> n >> m >> q;

    vector<vector<int>> g(n);

    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[y].push_back(x);
    }

    vector<array<int, 2>> s;

    segtree st(n);
    vector<array<int, 3>> qu(q);
    vector<int> ans(q);

    for(int i=0; i<q; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        qu[i]={x, y, i};
    }

    sort(qu.begin(), qu.end(), [&](array<int, 3> a, array<int, 3> b){
        return a[1] < b[1];
    });

    int l = 0;
    for(auto [left, right, ind]: qu){

        while(l<=right){
            for(auto j: g[l]) st.update(j, l, j);
            l++;
        }
        if(st(left, right) < left) ans[ind]=0;
        else ans[ind]=1; 
    }

    for(int i=0; i<q; i++){
        if(ans[i]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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