95 WA#20,但是小的大样例都没过,知道错在那个模块
查看原帖
95 WA#20,但是小的大样例都没过,知道错在那个模块
396994
Winston12321_楼主2023/8/7 20:29

求扫描线部分的答案和std是一致的(ans1是对的

但ans2-ans3斜线暴力部分错了(比如color2比答案小2

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
int tid;
int n,m,q;
int la;
int ans1,ans2,ans3;
int t,a,b,c,d;
int tot,cnt,qoq;
int slx1[6],sly1[6],slx2[6],sly2[6];
int hx1[100010],hx2[100010],hy[100010],h;
int sy1[100010],sy2[100010],sx[100010],s;
int x[200010];
bool exi[6];
struct node{
	int x,y;
}pre;
bool operator <(node x1,node x2){return x1.x==x2.x?x1.y<x2.y:x1.x<x2.x;}
map<node,bool>vis;
struct edge{
	int y,x1,x2;
	int opt;
}e[200010];
bool cmp(edge x1,edge x2){return x1.y<x2.y;}
struct Seg{
	int len,sum;
}T[800010];
void pushup(int id,int l,int r)
{
	if(T[id].sum) T[id].len=x[r+1]-x[l];
	else if(l<r) T[id].len=T[id<<1].len+T[id<<1|1].len;
	else T[id].len=0;
}
void add(int id,int l,int r,int u,int v,int k)
{
	if(x[l]==u && x[r+1]==v) return T[id].sum+=k,pushup(id,l,r),void();
	int mid=l+r>>1;
	if(v<=x[mid+1]) add(id<<1,l,mid,u,v,k);
	else if(u>=x[mid+1]) add(id<<1|1,mid+1,r,u,v,k);
	else
	{
		add(id<<1,l,mid,u,x[mid+1],k);
		add(id<<1|1,mid+1,r,x[mid+1],v,k);
	}
	pushup(id,l,r);
}
signed main()
{
	cin>>tid;
	cin>>n>>m>>q;
	for(int i=1;i<=q;++i)
	{
		cin>>t>>a>>b>>c>>d;
		if(t==3)
		{
			++qoq;
			slx1[qoq]=a,sly1[qoq]=b;
			slx2[qoq]=c,sly2[qoq]=d;
			continue;
		}
		if(t==1) hx1[++h]=a,hx2[h]=c,hy[h]=b;
		else sy1[++s]=b,sy2[s]=d,sx[s]=a;
		x[++tot]=a,x[++tot]=c+1;
		e[++cnt].opt=1;
		e[cnt].x1=a,e[cnt].x2=c+1,e[cnt].y=b;
		e[++cnt].opt=-1;
		e[cnt].x1=a,e[cnt].x2=c+1,e[cnt].y=d+1;
	}
	sort(x+1,x+tot+1);
	m=unique(x+1,x+tot+1)-x-1;
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<cnt;++i)
	{
		add(1,1,m-1,e[i].x1,e[i].x2,e[i].opt);
		ans1+=(e[i+1].y-e[i].y)*T[1].len;
	}
	for(int i=1;i<=qoq;++i)
	{
		for(int j=1;j<i;++j) if(!exi[j] && sly1[j]-slx1[j]==sly1[i]-slx1[i])
		{
			if(slx1[j]<=slx1[i] && slx2[i]<=slx2[j]) {exi[i]=1;break;}
			if(slx1[j]>=slx1[i] && slx2[i]>=slx2[j]) exi[j]=1,ans2-=slx2[j]-slx1[j]+1;
			else if(slx1[i]<=slx2[j] && slx1[i]>slx1[j]) slx1[i]=slx2[j]+1;
			else if(slx2[i]<slx2[j] && slx2[i]>=slx1[j]) slx2[i]=slx1[j]-1;
		}
		if(!exi[i]) ans2+=slx2[i]-slx1[i]+1;
	}
	for(int i=1;i<=qoq;++i) if(!exi[i])
	{
		for(int j=1;j<=h;++j)
		{
			pre.y=hy[j];
			pre.x=hy[j]-sly1[i]+slx1[i];
			if(hx1[j]<=pre.x && pre.x<=hx2[j] && slx1[i]<=pre.x && pre.x<=slx2[i])
				if(!vis[pre]) vis[pre]=1,++ans3;
		}
		for(int j=1;j<=s;++j)
		{
			pre.x=sx[j];
			pre.y=sx[j]+sly1[i]-slx1[i];
			if(sy1[j]<=pre.y && pre.y<=sy2[j] && sly1[i]<=pre.y && pre.y<=sly2[i])
				if(!vis[pre]) vis[pre]=1,++ans3;
		}
	}
	cout<<ans1+ans2-ans3<<'\n';
	return 0;
}
2023/8/7 20:29
加载中...