Submission #886027

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

    segtree(vector<int>a){
        n = a.size();
        val = a;
        st.resize(4*n, base);

        build(1, 0, n-1);
    }

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

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

    int get(int v, int l, int r){
        if(l>tr || r<tl) return base;
        else if(l>=tl&&r<=tr) return st[v];
        else{
            int mid = (l+r) / 2;
            return 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[x].push_back(y);
        ma[y] = max(ma[y], x);
        mi[x] = min(mi[x], y);
    }

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

    for(int i=0; i<n; i++){
        while(s.size() && s.back()[1] <= i) s.pop_back();
        if(s.size()) a[i] = s.back()[0];
    }

    segtree st(a);

    while(q--){
        int l, r; cin >> l >> r; l--; r--;
        if(ma[r] < l || mi[l] > r) cout<<"NO\n";
        else if(st(l+1, r-1) < l) cout<<"NO\n";
        else cout<<"YES\n";
    }
}

Compilation message (stderr)

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