제출 #1192638

#제출 시각아이디문제언어결과실행 시간메모리
1192638thaibeo123Curtains (NOI23_curtains)C++20
100 / 100
874 ms68652 KiB
#include <bits/stdc++.h>
using namespace std;

#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define countbit(x) (__builtin_popcountll(x))

const int N = 5e5 + 5;

int n, m, q;
int ans[N];
vector<int> line[N];
vector<pair<int, int>> query[N];

struct SegmentTree {
    vector<int> st, lazy;

    SegmentTree() {}
    SegmentTree(int n): st(n << 2 | 3), lazy(n << 2 | 3 ) {}

    void down(int x) {
        lazy[x << 1] = max(lazy[x << 1], lazy[x]);
        lazy[x << 1 | 1] = max(lazy[x << 1 | 1], lazy[x]);
        st[x << 1] = max(st[x << 1], lazy[x]);
        st[x << 1 | 1] = max(st[x << 1 | 1], lazy[x]);
    }

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

    int get(int u, int v, int l = 1, int r = n, int x = 1) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return st[x];
        int mid = (l + r) >> 1;
        down(x);
        if (v <= mid) return get(u, v, l, mid, x << 1);
        if (u > mid) return get(u, v, mid + 1, r, x << 1 | 1);
        return min(get(u, v, l, mid, x << 1), get(u, v, mid + 1, r, x << 1 | 1));
    }
};
SegmentTree st;

void input() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        line[r].pb(l);
    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        query[r].pb({l, i});
    }
    st = SegmentTree(n);
}

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int x : line[i]) {
            st.update(x, i, x);
        }
        for (auto x : query[i]) {
            int l = x.fi, id = x.se;
            ans[id] = (st.get(l, i) >= l);
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << (ans[i] ? "YES" : "NO") << "\n";
    }
}

int main() {
    if (fopen(NAME".INP", "r")) {
        freopen(NAME".INP", "r", stdin);
        freopen(NAME".OUT", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        input();
        solve();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

curtains.cpp: In function 'int main()':
curtains.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(NAME".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(NAME".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...