Submission #1088716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088716		vladilius	Curtains (NOI23_curtains)	C++17	24 / 100	1551 ms	22136 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    vector<int> a;
    int n;
    ST(int ns){
        n = ns;
        a.resize(n + 1);
    }
    void chmax(int l, int r, int x){
        for (int i = l; i <= r; i++){
            a[i] = max(a[i], x);
        }
    }
    int get(int l, int r){
        int mn = n + 1;
        for (int i = l; i <= r; i++){
            mn = min(mn, a[i]);
        }
        return mn;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> st[n + 1];
    while (m--){
        int l, r; cin>>l>>r;
        st[r].pb(l);
    }
    vector<pii> qs[n + 1];
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        qs[r].pb({l, i});
    }
    vector<int> out(q + 1);
    ST T(n);
    for (int r = 1; r <= n; r++){
        for (int l: st[r]){
            T.chmax(l, r, l);
        }
        for (auto [l, i]: qs[r]){
            out[i] = (T.get(l, r) >= l);
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<(out[i] ? "YES" : "NO")<<"\n";
    }
}

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