Submission #1315843

#TimeUsernameProblemLanguageResultExecution timeMemory
1315843nguyenkhangninh99Curtains (NOI23_curtains)C++20
100 / 100
721 ms74704 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 5e5 + 5;
int st[4 * maxn], lazy[4 * maxn];
void apply(int id, int val){
    lazy[id] = max(lazy[id], val);
    st[id] = max(st[id], val);
}
void push(int id){
    apply(id * 2, lazy[id]);
    apply(id * 2 + 1, lazy[id]);
}
void update(int id, int l, int r, int u, int v, int val){
    if(u <= l && r <= v) apply(id, val);
    else{
        push(id);
        int mid = (l + r) / 2;
        if(u <= mid) update(id * 2, l, mid, u, v, val);
        if(mid + 1 <= v) update(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }
}
int query(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 1e18;
    if(u <= l && r <= v) return st[id];
    int mid = (l + r) / 2;
    return min(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    vector<vector<int>> at(n + 1);
    for(int i = 1; i <= m; i++){
        int l, r; cin >> l >> r;
        at[r].push_back(l);
    }

    vector<vector<pair<int, int>>> qry(n + 1);

    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        qry[r].push_back({l, i});
    }

    vector<int> ans(q + 1);
    for(int i = 1; i <= n; i++){
        for(int j: at[i]) update(1, 1, n, j, i, j);
        for(auto [l, id]: qry[i]) ans[id] = (query(1, 1, n, l, i) == l);
    }
    
    for(int i = 1; i <= q; i++) cout << (ans[i] ? "YES" : "NO") << "\n";
    //update(l...r) for i: l->r a[i] = max(a[i], l);
    //query(l...r) for i: l->r query min
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...