记录编号	187760	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2015-09-20 19:38:37	内存使用	2.23 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=2*5000+100,INF=10011,SIZEM=20*INF;
int tot=0,sum[SIZEM],co[SIZEM];
int N,xd,yd,xu,yu,ans=0;
class miku
{
	public:
	int x1,y1,x2,y2;
	bool type;
	miku(){}
	miku(int a,int b,int c,int d,bool t)
	{
		x1=a,y1=b,x2=c,y2=d,type=t;
	}
};
miku xline[SIZEN];
miku yline[SIZEN];
bool cmp1(miku a,miku b)
{
	return a.y1<b.y1;
}
bool cmp2(miku a,miku b)
{
	return a.x1<b.x1;
}
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d%d%d",&xd,&yd,&xu,&yu);
		xline[++tot]=miku(xd,yd,xu,yd,1);
		yline[tot]=miku(xd,yd,xd,yu,1);
		xline[++tot]=miku(xd,yu,xu,yu,0);
		yline[tot]=miku(xu,yd,xu,yu,0);
	}
	sort(xline+1,xline+tot+1,cmp1);
	sort(yline+1,yline+tot+1,cmp2);
}
void make(int x,int l,int r)
{
	if(co[x]) sum[x]=r-l+1;
	else if(l==r) sum[x]=0;
	else sum[x]=sum[x<<1]+sum[x<<1|1];
}
void change(int x,int l,int r,int px,int py,bool type)
{
	if(px>r||py<l) return;
	if(px<=l&&r<=py)
	{
		if(type==0) co[x]--;
		else co[x]++;
		make(x,l,r);
		//if(l==1&&r==2) cout<<sum[x]<<" "<<endl;
		return;
	}
	int mid=(l+r)>>1;
	if(px<=mid)change(x<<1,l,mid,px,py,type);
	if(py>mid) change(x<<1|1,mid+1,r,px,py,type);
	make(x,l,r);
}
void work()
{
	memset(sum,0,sizeof(sum));
	memset(co,0,sizeof(co));
	int last=0;
	for(int i=1;i<=tot;i++)
	{
		change(1,-INF,INF,xline[i].x1,xline[i].x2-1,xline[i].type);
		ans+=abs(sum[1]-last);last=sum[1];
	}
	memset(sum,0,sizeof(sum));
	memset(co,0,sizeof(co));
	last=0;
	for(int i=1;i<=tot;i++)
	{
		change(1,-INF,INF,yline[i].y1,yline[i].y2-1,yline[i].type);
		ans+=abs(sum[1]-last);last=sum[1];
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	read();
	work();
	return 0;
}