Submission #914256

#	Time	Username	Problem	Language	Result	Execution time	Memory
914256		esomer	Curtains (NOI23_curtains)	C++17	100 / 100	860 ms	70580 KiB

curtains

#include<bits/stdc++.h>
 
using namespace std;

struct segTree{
    vector<int> v, upd;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        v.assign(2 * sz, 1e9);
        upd.assign(2 * sz, 1e9);
    }
    void set(int l, int r, int val, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            v[x] = min(val, v[x]);
            upd[x] = min(val, upd[x]);
            return;
        }else if(lx >= r || rx <= l) return;
        int m = (lx + rx) / 2;
        set(l, r, val, 2 * x + 1, lx, m);
        set(l, r, val, 2 * x + 2, m, rx);
        v[x] = min(max(v[2 * x + 1], v[2 * x + 2]), upd[x]);
    }

    void set(int l, int r, int val){
        set(l, r, val, 0, 0, sz);
    }

    int compare(int a, int b){
        if(a == 2e9) return b;
        else if(b == 2e9) return a;
        else return max(a, b);
    }

    int calc(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return v[x];
        else if(lx >= r || rx <= l) return 2e9;
        int m = (lx + rx) / 2;
        int c1 = calc(l, r, 2 * x + 1, lx, m);
        int c2 = calc(l, r, 2 * x + 2, m, rx);
        // cout << "x "<< x << " lx "<< lx << " rx "<< rx << " v[x] "<< v[x] << " upd[x] "<< upd[x] << " c1 "<< c1 << " c2 "<< c2 << "\n";
        return min(compare(c1, c2), upd[x]);
    }

    int calc(int l, int r){
        return calc(l, r, 0, 0, sz);
    }
};

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> startCurtain(n);
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r; l--; r--;
        startCurtain[l].push_back(r);
    }
    vector<vector<int>> startQuery(n);
    vector<pair<int, int>> queries(q);
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r; l--; r--;
        queries[i] = {l, r};
        startQuery[l].push_back(i);
    }
    segTree st; st.init(n);
    vector<bool> ans(q);
    for(int i = n - 1; i >= 0; i--){
        for(int r : startCurtain[i]){
            // cout << "add "<< i << " "<< r << " " << endl;
            st.set(i, r + 1, r);
        }
        for(int j : startQuery[i]){
            int l = queries[j].first;
            int r = queries[j].second;
            // cout << "l "<< l << " r "<< r << " calc "<< st.calc(l, r + 1) << "\n";
            if(st.calc(l, r + 1) <= r) ans[j] = true;
            else ans[j] = false;
        }
    }
    for(bool b : ans){
        if(b) cout << "YES\n";
        else cout << "NO\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
}

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