Submission #1314920

#TimeUsernameProblemLanguageResultExecution timeMemory
1314920baodatCurtains (NOI23_curtains)C++20
100 / 100
556 ms27724 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin() + 1, (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
int n, m, q;

struct segment_tree {
    int _n;
    vector<int> _st, _lazy;
    segment_tree(int n = 0) {
        init(n);
    }
    void init(int n) {
        _n = n;
        _st.assign(4 * _n + 5, -2e9);
        _lazy.assign(4 * _n + 5, -2e9);
    }
    void apply(int i, int v){
    	_st[i] = max(_st[i], v);
    	_lazy[i] = max(_lazy[i], v);
    }
    void down(int i){
    	if(_lazy[i] == -2e9) return;
    	int cl = (i << 1), cr = (cl | 1);
    	apply(cl, _lazy[i]);
    	apply(cr, _lazy[i]);
    	_lazy[i] = -2e9;
    }

    void update(int i, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
        	apply(i, val);
            return;
        }
        down(i);
        int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
        update(cl, l, m, u, v, val);
        update(cr, m + 1, r, u, v, val);
        _st[i] = min(_st[i << 1], _st[i << 1 | 1]);
    }
    int query(int i, int l, int r, int u, int v) {
        if (l > v || r < u) return 2e9;
        if (l >= u && r <= v) return _st[i];
        down(i);
        int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
        return min(query(cl, l, m, u, v), query(cr, m + 1, r, u, v));
    }
};
struct Data{
	int from, to, id;
};

void solve(){
	cin >> n >> m >> q;
	vector<pair<int, int>> curtain(m + 1);
	FOR(i, 1, m) cin >> curtain[i].first >> curtain[i].second;
	vector<Data> queries(q + 1);
	FOR(i, 1, q) cin >> queries[i].from >> queries[i].to, queries[i].id = i;
	sort(all_1(curtain), [&](pair<int, int> a, pair<int, int> b){
		return a.second < b.second || (a.second == b.second && a.first < b.first);
	});
	sort(all_1(queries), [&](Data a, Data b){
		return a.to < b.to || (a.to == b.to && a.from < b.from);
	});
	segment_tree st(n);
	vector<bool>ans(q + 1);
	int j = 1;
	FOR(qr, 1, q){
		auto [from, to, id] = queries[qr];
        while (j <= m && curtain[j].second <= to) {
            st.update(1, 1, n, curtain[j].first, curtain[j].second, curtain[j].first);
            ++j;
        }
        ans[id] = (st.query(1, 1, n, from, to) >= from);
	}
	FOR(i, 1, q) cout << (ans[i] ? "YES\n" : "NO\n");
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	return 0;
}
/*
n san khau, m man
man i che l[i] -> r[i]
truy van j, yeu can che doan from[j] -> to[j]
from[j] -> to[j]
l[i] < from[j] || r[i] > to[j] -> continue
=> l[i] >= from[j] && r[i] <= to[j] -> thang nao cung dc
gia su ta co dinh dc to[j]
chi quan tam max cua r[j], 
*/
#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...