CDQ 分治 WA第2个点 答案为1 输出是3
  • 板块CF12D Ball
  • 楼主Shadow_Lord
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/24 19:18
  • 上次更新2023/10/23 14:52:03
查看原帖
CDQ 分治 WA第2个点 答案为1 输出是3
648756
Shadow_Lord楼主2023/5/24 19:18
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>'0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int n,ans;
bool die[N];
struct node{
	int a,b,c,id;
}e[N];
bool cmp1(node a,node b)
{
	return a.a>b.a;
}
bool cmp2(node a,node b)
{
	return a.b>b.b;
}
inline void f(int l,int r)
{
	if(l==r)return ;
	int mid=(l+r)>>1,m1=0,m2=0;f(l,mid);f(mid+1,r);
	sort(e+l,e+mid+1,cmp2);sort(e+mid+1,e+r+1,cmp2);
	for(int i=mid+1,j=l;i<=r;i++)
	{
		while(j<=mid&&e[j].b>e[i].b)
		{
			m1=max(m1,e[j].c);
			if(e[j].a>e[mid].a)
			{
				m2=max(m2,e[j].c);
			}
			j++;
		}
		if(e[i].a==e[mid].a)
		{
			if(m2>e[i].c) die[e[i].id]=1;
		}
		else
		{
			if(m1>e[i].c) die[e[i].id]=1;
		}
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		e[i].a=read();
		e[i].id=i;
	}
	for(int i=1;i<=n;i++)
	{
		e[i].b=read();
	}
	for(int i=1;i<=n;i++)
	{
		e[i].c=read();
	}
	sort(e+1,e+n+1,cmp1);
	f(1,n);
	for(int i=1;i<=n;i++)if(die[i])ans++;
	cout<<ans;
	return 0;
}
2023/5/24 19:18
加载中...