[原创]HDU 6012 Lotus and Horticulture [离散化+前缀和处理]【思维】

# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 50000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}


/***********************************************************************/
struct input{
    int l,r,a,b,c;
}a[N];
int lr[N<<1],cnt;
LL rr[N<<1],ll[N<<1];

int h(int x){
    int l=0,r=cnt,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(lr[mid]<=x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int main(){
    int _;
    s1(_);
    while(_--){
        int n;
        s1(n);
        cnt = 0;

        Rep(i,1,n) {
            a[i].l=read();
            a[i].r=read();
            a[i].a=read();
            a[i].b=read();
            a[i].c=read();

            lr[++cnt]=a[i].l;
            lr[++cnt]=a[i].r;
        }
        sort(lr+1,lr+n*2+1);
        cnt = unique(lr+1,lr+n*2+1)-(lr+1);
        //Rep(i,1,cnt){printf("%d\n",lr[i]);}

        Rep(i,0,cnt)  rr[i]=ll[i]=0ll;

        LL ans = 0ll,mx = 0ll;
        Rep(i,1,n){
            ans+=a[i].c;
            rr[h(a[i].l)]+=a[i].a-a[i].c;
            ll[h(a[i].r)]+=a[i].b-a[i].a;
        }

        mx=ans;
        Rep(i,1,cnt){
            ans+=rr[i];
            mx=max(mx,ans);
            ans+=ll[i];
            mx=max(mx,ans);
        }
        printf("%I64d\n",mx);
    }
    return 0;
}