比赛 2025.3.6 评测结果 AAAAA
题目名称 矩形周长 最终得分 100
用户昵称 flyfree 运行时间 0.035 s
代码语言 C++ 内存使用 3.49 MiB
提交时间 2025-03-06 20:32:41
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 20010
#define inf 10000
#define qmod(x) (x>mod?x-mod:x)
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll h,l,r,val;
}qs[MAXN];
bool cmp(node a,node b){
	return a.h==b.h?a.val>b.val:a.h<b.h;
}
ll n,cnt[MAXN],ans,p;
ll modify(ll lz,ll rz,ll val){
	ll res=0;
	for(int i=lz;i<=rz;i++){
		if(val==1){
			if(!cnt[i])res++;
			cnt[i]++;
		}else{
			cnt[i]--;
			if(!cnt[i])res++;
		}
	}
	return res;
}
ll calc(){
	ll res=0,pd=0;
	for(int i=1;i<=2*inf;i++){
		if(cnt[i]){
			if(!pd)pd=1,res++;
		}else{
			pd=0;
		}
	}
	return res+pd;
}
int main(){
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		ll x_1=read()+inf,y_1=read(),x_2=read()+inf-1,y_2=read();
		qs[i*2-1].h=y_1,qs[i*2-1].l=x_1,qs[i*2-1].r=x_2,qs[i*2-1].val=1;
		qs[i*2].h=y_2,qs[i*2].l=x_1,qs[i*2].r=x_2,qs[i*2].val=-1;
	}
	sort(qs+1,qs+1+2*n,cmp);
	for(int i=1;i<=2*n;i++){
		ans+=modify(qs[i].l,qs[i].r,qs[i].val);
		if(qs[i].h!=qs[i+1].h&&i!=2*n){
			ans+=(qs[i+1].h-qs[i].h)*calc()*2;
//			p+=(qs[i+1].h-qs[i].h)*calc()*2;
//			cout<<qs[i].h<<" "<<calc()<<endl;
		}
	}
//	cout<<ans<<" "<<p<<endl;
	cout<<ans<<endl;
	return 0;
}