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

发布于 2022-08-14  378 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-14