求调昨晚 ABC F
  • 板块学术版
  • 楼主roger_yrj
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/9 07:33
  • 上次更新2023/11/3 10:58:24
查看原帖
求调昨晚 ABC F
367521
roger_yrj楼主2023/7/9 07:33
#include<bits/stdc++.h>
#define ls(k) k<<1
#define rs(k) (k<<1)+1
using namespace std;
const int N=2e6+10;
int n,m,num[3*N];
map<int,int>id;
int minn[12*N];
void updata(int k,int x,int l,int r,int y){
	if(x<l||r<x)return;
	if(l<=x&&x<=r)minn[k]=min(minn[k],y);
	if(l==r)return;
	int mid=l+r>>1;
	updata(ls(k),x,l,mid,y);
	updata(rs(k),x,mid+1,r,y);
}
int query(int k,int L,int R,int l,int r){
	if(r<L||R<l)return 1145141919;
	if(L<=l&&r<=R)return minn[k];
	int mid=l+r>>1;
	return min(query(ls(k),L,R,l,mid),query(rs(k),L,R,mid+1,r));
}
struct s{
	int x,y,z;
}a[N];
bool operator<(s x,s y){
	if(x.x!=y.x)return x.x<y.x;
	if(x.y!=y.y)return x.y<y.y;
	return x.z<y.z;
}
int main(){
	memset(minn,0x7f,sizeof(minn));
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
		num[++m]=a[i].x,num[++m]=a[i].y,num[++m]=a[i].z;
		if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
		if(a[i].y>a[i].z)swap(a[i].y,a[i].z);
		if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
	}
	sort(a+1,a+n+1);
	sort(num+1,num+m+1);
	m=unique(num+1,num+m+1)-num-1;
	for(int i=1;i<=m;i++)id[num[i]]=i;
	for(int i=1;i<=n;i++){
		a[i].x=id[a[i].x];
		a[i].y=id[a[i].y];
		a[i].z=id[a[i].z];
	}
	for(int i=1,lst=1;i<=n;i++){
		if(a[i].x!=a[i-1].x){
			if(i>1){
				for(int j=lst;j<i;j++)updata(1,a[i].y,1,m,a[i].z);
			}
			lst=i;
		}
		if(query(1,1,a[i].y-1,1,m)<a[i].z){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
}

AC×60\colorbox{green}{\textcolor{white}{AC}}\times60

WA×4\colorbox{gold}{\textcolor{white}{WA}}\times4

2023/7/9 07:33
加载中...