90分求助,第四个点一直WA
查看原帖
90分求助,第四个点一直WA
109089
Daredevil楼主2020/5/5 07:57
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct data
{
	int x,y,op,k;
}p[3000015],tmp[3000015];
int n,m,tot,ans[3000015];
bool cmp(data a,data b)
{
	if(a.x==b.x&&a.y==b.y)
		return a.op<b.op;
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}
void cdq(int l,int r)
{
	if(l==r)
		return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int i=l,j=mid+1,cnt=0,k=0;
	while(i<=mid&&j<=r)
	{
		if(p[i].y<=p[j].y)
		{
			if(p[i].op==0)
				cnt++;
			tmp[++k]=p[i++];
		}
		else
		{
			ans[p[j].k]+=cnt;
			tmp[++k]=p[j++];
		}
	}
	while(i<=mid)
		tmp[++k]=p[i++];
	while(j<=r)
	{
		ans[p[j].k]+=cnt;
		tmp[++k]=p[j++];
	}
	for(int t=1;t<=k;t++)
		p[l+t-1]=tmp[t];
}
int main()
{
	scanf("%d%d",&n,&m);
	if(n==0||m==0)
		return 0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&p[i].x,&p[i].y);
		p[i].op=0;
		p[i].k=0;
	}
	tot=n;
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		p[++tot]=(data){a-1,b-1,1,tot};
		p[++tot]=(data){a-1,d,1,tot};
		p[++tot]=(data){c,b-1,1,tot};
		p[++tot]=(data){c,d,1,tot};
	}
	sort(p+1,p+tot+1,cmp);
	cdq(1,tot);
	for(int i=n+1;i+3<=tot;i+=4)
	{
		int a=i,b=i+1,c=i+2,d=i+3;
		printf("%d\n",ans[d]-ans[c]-ans[b]+ans[a]);
	}
	return 0;
}
2020/5/5 07:57
加载中...