求调 ABC D(玄关)
  • 板块灌水区
  • 楼主cqbzcjh
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/28 21:48
  • 上次更新2024/12/29 10:45:53
查看原帖
求调 ABC D(玄关)
906854
cqbzcjh楼主2024/12/28 21:48
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,cnt,tot;
struct node{
	int x,y;
}b[N],w[N];
struct node2{
	int v,p;
}minn[N];
//vector<node> b,w;
bool cmp(node a,node b){
//	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		char c;
		cin>>x>>y>>c;
		if(c=='B'){
			b[++cnt]={x,y};
		}else if(c=='W'){
			w[++tot]={x,y};
		}
	}
	sort(w+1,w+tot+1,cmp);
	minn[1]={w[1].y,1};
	for(int i=2;i<=tot;i++){
		if(w[i].y<=minn[i-1].v){
			minn[i]={w[i].y,i};
		}else minn[i]=minn[i-1];
	}
	for(int i=1;i<=cnt;i++){
//		int p=upper_bound(w+1,w+tot+1,b[i].x)-w-1;
		int l=1,r=tot;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(w[mid].x<=b[i].x){
				l=mid;
			}else{
				r=mid-1;
			}
		}
		if(w[l].x>b[i].x)continue;
		if(minn[l].v<=b[i].y&&w[minn[l].p].x<=b[i].x){
			cout<<"No\n";
			return 0;
		}
	}
	cout<<"Yes\n";
	return 0;
}

自己写复杂了,用的二分,但是理论上是能过的。只 WA 了 5 个点。submission

2024/12/28 21:48
加载中...