제출 #1262095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262095		rayan_bd	Curtains (NOI23_curtains)	C++20	100 / 100	1321 ms	114040 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
const int mxN = 5e5 + 1000;
const int INF = 1e9;
int seg[mxN * 4], lz[mxN * 4];
void push(int node, int start, int end){
    seg[node] = max(seg[node], lz[node]);
    if(start != end) lz[node * 2 + 1] = max(lz[node * 2 + 1], lz[node]);
    if(start != end) lz[node * 2 + 2] = max(lz[node * 2 + 2], lz[node]);
    lz[node] = 0;
}
void upd(int node, int start, int end, int l, int r, int v){
    push(node, start, end);
    if(start > r || end < l) return;
    if(start >= l && end <= r){
        lz[node] = max(lz[node], v);
        push(node, start, end);
        return;
    }
    int mid = start + (end - start) / 2;
    upd(node * 2 + 1, start, mid, l, r, v);
    upd(node * 2 + 2, mid + 1, end, l, r, v);
    seg[node] = min(seg[node * 2 + 1], seg[node * 2 + 2]);
}
int query(int node, int start, int end, int l, int r){
    push(node, start, end);
    if(start > r || end < l) return INF;
    if(start >= l && end <= r) return seg[node];
    int mid = start + (end - start) / 2;
    return min(query(node * 2 + 1, start, mid, l, r), query(node * 2 + 2, mid + 1, end, l, r));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q, l, r;
    cin >> n >> m >> q;
    vector<bool> ok(q + 1, 0);
    map<int, vector<int>> range;
    map<int, vector<pair<int, int>>> queries;
    for(int i = 1; i <= m; ++i){
        cin >> l >> r;
        range[r].push_back(l);
    }
    for(int i = 1; i <= q; ++i){
        cin >> l >> r;
        queries[r].push_back({l, i});
    }
    for(int i = 1; i <= n; ++i){
        for(auto it : range[i]) upd(0, 1, n, it, i, it);
        for(auto it : queries[i]){
            ok[it.second] = (query(0, 1, n, it.first, i) == it.first);
        }
    }
    for(int i = 1; i <= q; ++i){
        if(ok[i]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

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