比赛 |
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;
}