School 小白月赛54 C

C-School_牛客小白月赛54 (nowcoder.com)

给你一个为h小时m分钟的一天，给你abcd表示a小时b分钟到c小时d分钟不能打电话，给你q个询问，问你这个时刻可不可以打电话

正解：区间合并+二分

像这种有关时间的题，最好统一单位叭，都化成分钟

然后就相当于在这一个区间内不可以打电话，然后把这n个区间合并，看看q个询问里面的时刻也就是一个点在不在区间里面，在就no 不在就yes

那怎么知道在不在区间里面呢，想到用二分

找到大于这个数的第一个区间的左端点，然后这个区间的上一个区间的右端点是否大于等于x，如果是则no，不是则yes

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PAII;
const int N=2e6+10,M=5050,INF=0x3f3f3f3f,mod=1e7+7;
vector<PAII> res,segs;
bool cmp(PAII x,PAII y)
{
	return x.first<y.first;
}
void merge(vector<PAII> &segs)
{
	sort(segs.begin(),segs.end());
	ll st=-1e18,ed=-1e18;
	for(auto it:segs)
	{
		if(it.first>ed)
		{
			if(st!=-1e18) res.push_back({st,ed});
			st=it.first,ed=it.second;
		}
		else ed=max(ed,it.second);
	}
	if(st!=-1e18) res.push_back({st,ed});
	segs=res;
}
int main(){
    IOS; 
    int T;
    T=1;
    //cin>>T;
    while(T--)
    {   
		ll n,h,m,q;
		cin>>n>>h>>m>>q;
		for(int i=1;i<=n;i++)
		{
			ll a,b,c,d;
			cin>>a>>b>>c>>d;
			ll l=a*m+b;
			ll r=c*m+d;
			segs.push_back({l,r});
		}
		merge(segs);
		while(q--)
		{
			ll a,b;
			cin>>a>>b;
			ll x=a*m+b;
			ll l=0,r=segs.size();
			while(l<r)
			{
				int mid=l+r>>1;
				if(segs[mid].first>x) r=mid;
				else l=mid+1; 
			}
			int pos=l;
			if(segs[pos-1].second>=x) cout<<"Non";
			else cout<<"Yesn";
		}
		 
    }
    return 0;
}
/*


*/

最后

以上就是积极盼望为你收集整理的School 小白月赛54 C的全部内容，希望文章能够帮你解决School 小白月赛54 C所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。