제출 #1169566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169566		trashaccount	Curtains (NOI23_curtains)	C++20	100 / 100	779 ms	68308 KiB

curtains

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

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 5e5, inf = 1e9+7;

int n, m, q, st[4*NM+5], lazy[4*NM+5];
vector <int> upd[NM+5];
vector <pii> qry[NM+5];
bool ans[NM+5];

void down(int id){
    if (lazy[id] == +inf) return;
    st[2*id] = min(st[2*id], lazy[id]), st[2*id+1] = min(st[2*id+1], lazy[id]);
    lazy[2*id] = min(lazy[2*id], lazy[id]), lazy[2*id+1] = min(lazy[2*id+1], lazy[id]);
    lazy[id] = +inf;
}

void update(int id, int l, int r, int u, int v, int val){
    if (v < l || u > r) return;
    if (l >= u && r <= v){
        st[id] = min(st[id], val);
        lazy[id] = min(lazy[id], val);
        return;
    }
    down(id);
    int mid = (l+r)/2;
    update(2*id, l, mid, u, v, val);
    update(2*id+1, mid+1, r, u, v, val);
    st[id] = max(st[2*id], st[2*id+1]);
}

int get(int id, int l, int r, int u, int v){
    if (v < l || u > r) return 0;
    if (l >= u && r <= v) return st[id];
    down(id);
    int mid = (l+r)/2;
    return max(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v));
}

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

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        upd[u].push_back(v);
    }
    for (int i = 1; i <= q; i++){
        int s, e; cin >> s >> e;
        qry[s].push_back(mp(e, i));
    }
    for (int i = 1; i <= 4*n; i++) st[i] = lazy[i] = +inf;

    for (int i = n; i >= 1; i--){
        for (int j : upd[i]) update(1, 1, n, i, j, j);
        for (pii p : qry[i]){
            if (get(1, 1, n, i, p.fi) == p.fi) ans[p.se] = 1;
        }
    }
    for (int i = 1; i <= q; i++)
        cout << (ans[i] ? "YES\n" : "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