[牛客小白月赛54]C.School（区间合并 + 二分）

题目传送门：C-School_牛客小白月赛54 (nowcoder.com)

思路 / Thought

一般遇到时间的题，都会将单位统一化，比如统一成“分钟”，那么这么的a时b分，就相当于是第a * m + b分钟。问题就转化成了给定一个1e13规模的区域，有1e3个区间，然后给定一个点问是否在这些区间覆盖的地方。

先读入区间，根据左端点排序，然后将区间合并成互不相交的若干个区间。

最后判断x点是否被覆盖了，只需要找到最后一个小于等于x的左端点（第一个大于x的左端点的前一个），判断右端点是否大于等于x即可。

代码 / Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

void solve()
{
	int n, h, m, q;cin >> n >> h >> m >> q;
	vector<pair<int, int> > v, t;//t是合并后的区间数组
	for(int i = 1;i <= n; ++ i)
	{
		int a, b, c, d;cin >> a >> b >> c >> d;
		a = a * m + b, c = c * m + d;
		v.push_back({a, c});
	}
	sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.fi < b.fi;});
	t.push_back(v[0]);
	for(auto &i : v)
	{
		if(i.fi <= t.back().se)t.back().se = max(t.back().se, i.se);
		else t.push_back(i);
	}
	while(q --)
	{
		int x, y;cin >> x >> y;
		x = x * m + y;
		int pos = upper_bound(t.begin(), t.end(), x, [](const int &a, const pair<int, int> &b){return a < b.fi;}) - t.begin() - 1;
		if(pos < t.size() && t[pos].fi <= x && x <= t[pos].se)cout << "No" << '\n';
		else cout << "Yes" << '\n';
	}
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}