【jzoj5334】【NOIP2017提高A组模拟8.24】【空】【扫描线】【set】

description

solution

考虑用扫描线，可以发现有相交和内含两种情况，相交就是l+r的差，内含就是r-l的差，可以分别两次用set维护。

code

#include<set>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=2*1e5+9,inf=1e9+7;
int n,l[mn],r[mn];
struct rec{
int x,v,op;
friend bool operator<(rec x,rec y){
return (x.x<y.x)||((x.x==y.x)&&(x.op>y.op));
    }
};
rec a[mn*2];
multiset<int>s;
int max(int x,int y){
return (x>y)?x:y;
}
int calc(int op){
int cnt=0;
    fo(i,1,n){
        a[++cnt].x=l[i];
        a[cnt].v=op*l[i]+r[i];
        a[cnt].op=1;
        a[++cnt].x=r[i];
        a[cnt].v=-op*l[i]-r[i];
        a[cnt].op=-1;
    }
    sort(a+1,a+cnt+1);
int ans=0;
    fo(i,1,cnt)if(a[i].op>0)s.insert(a[i].v);
else{
        ans=max(ans,(*(--s.end()))+a[i].v);
        s.erase(s.find(-a[i].v));
    }
return ans;
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
scanf("%d",&n);
    fo(i,1,n)scanf("%d%d",&l[i],&r[i]);
printf("%d",max(calc(1),calc(-1)));
return 0;
}