oj.uz

Submission #886027

# Submission time Handle Problem Language Result Execution time Memory
886027 2023-12-11T11:58:07 Z vjudge1 Curtains (NOI23_curtains) C++17
0 / 100
 1 ms 460 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Incorrect 0 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -