Submission #886044

#	Time	Username	Problem	Language	Result	Execution time	Memory
886044		vjudge1	Curtains (NOI23_curtains)	C++17	0 / 100	1 ms	348 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;
    int base = -1;

    segtree(vector<int>a){
        n = a.size();
        st.resize(4*n, -1);
        t.resize(4*n,-1);
        marked.resize(4*n);
    }

    void push(int v, int l, int r){
        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;
        else 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){
        if(r<l) return;
        tl = l; tr = r;
        update(1, 0, n-1, val);
    }

    int get(int v, int l, int 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){
        int tl = l, tr = r;

        if(r<l) return base;
        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);
    vector<int> vis(n, 0), ma(n, -1), mi(n, INF);


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

    vector<array<int, 2>> s;
    vector<int> a(n, -1);



    segtree st(a);
    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+1, l-1, j);
            l++;
        }
        if(ma[right] < left || mi[left] > right) ans[ind]=0;
        else if(st(left+1, right-1) < 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";
    }
}

Compilation message (stderr)

curtains.cpp: In member function 'long long int segtree::operator()(long long int, long long int)':
curtains.cpp:74:13: warning: unused variable 'tl' [-Wunused-variable]
   74 |         int tl = l, tr = r;
      |             ^~
curtains.cpp:74:21: warning: unused variable 'tr' [-Wunused-variable]
   74 |         int tl = l, tr = r;
      |                     ^~

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