Submission #1314900

#TimeUsernameProblemLanguageResultExecution timeMemory
1314900baodatCurtains (NOI23_curtains)C++20
44 / 100
1590 ms19644 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;
	segment_tree(int n = 0){
		init(n);
	}
	void init(int n){
		_n = n;
		_st.assign(4 * _n + 5, -2e9);
	}
	void update(int i, int l, int r, int pos, int val){
		if(pos > r || pos < l) return;
		if(l == r){
			_st[i] = max(_st[i], val);
			return;
		}
		int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
		update(cl, l, m, pos, val);
		update(cr, m + 1, r, pos, val);
		_st[i] = max(_st[cl], _st[cr]);
	}
	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];
		int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
		return max(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);
			++j;
		}
		int i = from;
		bool ok = true;
		while(i <= to){
			int maxi = st.query(1, 1, n, from, i);
			if(maxi < i){
				ok = false;
				break;
			}
			i = maxi + 1;
		}
		ans[id] = ok;
	}
	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...