全 WA 0pts,但样例过了
查看原帖
全 WA 0pts,但样例过了
621883
MushR楼主2024/1/5 13:49

rt.

照着第一篇题解改过一遍,还是0pts。

#include<bits/stdc++.h>
using namespace std;

#define int  long long

int n;
long long ans;
int X[200003],tot;

struct seg{
    int l,r,y,f;
}sg[200003];

bool cmp(seg a,seg b){
    return a.y<b.y;
}

struct segt{
    int l,r,sum,len;
}a[800003];

void build(int id,int left,int right){
    a[id].l=left,a[id].r=right;
    a[id].sum=a[id].len=0;

    if(left==right)
        return;

    int mid=(left+right)/2;
    build(id*2,left,mid);
    build(id*2+1,mid+1,right);
}

void pushup(int id){
    if(a[id].sum)
        a[id].len=X[a[id].r+1]-X[a[id].l];
    else
        a[id].len=a[id*2].len+a[id*2+1].len;
}

void add(int id,int left,int right,int k){
    if(X[a[id].r+1]<=left || X[a[id].l]>=right)
        return;

    if(X[a[id].l]>=left && X[a[id].r+1]<=right){
        a[id].sum+=k;
        pushup(id);
        return;
    }

    // if(X[a[id*2].r+1]>left)
        add(id*2,left,right,k);
    // if(X[a[id*2+1].l]<right)
        add(id*2+1,left,right,k);
    pushup(id);
}

signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x_1,x_2,y_1,y_2;
        scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
        X[2*i-1]=x_1,X[2*i]=x_2;
        sg[2*i-1]=seg{x_1,x_2,y_1,1};
        sg[2*i]=seg{x_1,x_2,y_2,-1};
    }

    sort(sg+1,sg+2*n+1,cmp);
    sort(X+1,X+2*n+1);
    tot=unique(X+1,X+2*n+1)-X-1;
    build(1,1,tot-1);

    for(int i=1;i<2*n;i++){
        add(1,sg[i].l,sg[i].r,sg[i].f);
        ans+=1ll*a[1].len*(sg[i+1].y-sg[i].y);
    }

    printf("%d\n",ans);
    return 0;
}
2024/1/5 13:49
加载中...