C++11(clang++ 3.9) 解法, 执行用时: 744ms, 内存消耗: 7048K, 提交时间: 2019-07-19 11:17:37

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100010;
const ll inf=1000000000000007ll;

#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l+r>>1)
ll mx[N<<2],ad[N<<2];
void pushup(int x){
	mx[x]=max(mx[ls],mx[rs]);
}
void pushdown(int x){
	ad[ls]+=ad[x];ad[rs]+=ad[x];
	mx[ls]+=ad[x];mx[rs]+=ad[x];
	ad[x]=0;
}
void build(int x,int l,int r){
	mx[x]=0;ad[x]=0;
	if(l==r)return ;
	build(ls,l,mid);build(rs,mid+1,r);
}
void add(int x,int l,int r,int L,int R,ll p){
	if(L>r||l>R)return ;
	if(L<=l&&r<=R){
		mx[x]+=p;ad[x]+=p;
		return ;
	}
	pushdown(x);
	add(ls,l,mid,L,R,p);
	add(rs,mid+1,r,L,R,p);
	pushup(x);
}
void change(int x,int l,int r,int pos,ll v){
	if(pos<l||pos>r)return ;
	if(l==r){
		mx[x]=max(mx[x],v);
		return ;
	}
	pushdown(x);
	change(ls,l,mid,pos,v);
	change(rs,mid+1,r,pos,v);
	pushup(x);
}
ll query(int x,int l,int r,int L,int R){
	if(L>r||l>R)return -inf;
	if(L<=l&&r<=R){
		return mx[x];
	}
	pushdown(x);
	return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int n;
struct E{
	int x,y,a,b;
}a[N];
bool comp(E A,E B){
	if(A.x==B.x)return A.y>B.y;
	return A.x<B.x;
}
int len,b[N];
int main(){
	while(~scanf("%d",&n)){
		len=0;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
			b[++len]=a[i].y;
		}
		sort(b+1,b+len+1);
		len=unique(b+1,b+n+1)-b-1;
		for(int i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b,a[i].y++;
		len++;
		build(1,1,len);
		sort(a+1,a+n+1,comp);
		for(int i=1;i<=n;i++){
			ll tmp=query(1,1,len,1,a[i].y);
			change(1,1,len,a[i].y,tmp+a[i].b);
			add(1,1,len,a[i].y+1,len,a[i].b);
			add(1,1,len,1,a[i].y-1,a[i].a);
		}
		printf("%lld\n",mx[1]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 840ms, 内存消耗: 23584K, 提交时间: 2019-08-13 10:30:15

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 400010
ll lazy[N<<2],mx[N<<2];
int L[N<<2],R[N<<2];
struct Poi{
	int a,b;
	int x,y;
	bool operator<(const Poi&p)const{return x==p.x?y>p.y:x<p.x;}
}a[N];
int b[N];
void pushup(int p){
	mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
void pushdown(int p){
	ll t=lazy[p];
	if(!t)return;
	if(L[p<<1])lazy[p<<1]+=t,mx[p<<1]+=t;
	if(L[p<<1|1])lazy[p<<1|1]+=t,mx[p<<1|1]+=t;
	lazy[p]=0;
}
void build(int p,int l,int r){
	L[p]=l,R[p]=r;
	int mid=(l+r)>>1;
	lazy[p]=0;mx[p]=-1e18;
	if(l==r)return;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void upd(int p,int pos,ll x){
	pushdown(p);
	if(L[p]>pos||R[p]<pos)return;
	if(L[p]==pos&&pos==R[p]){mx[p]=max(mx[p],x);return;}
	upd(p<<1,pos,x);
	upd(p<<1|1,pos,x);
	pushup(p);
}
void modify(int p,int l,int r,ll x){
	if(l<=L[p]&&r>=R[p]){
		lazy[p]+=x;
		mx[p]+=x;
		return;
	}
	if(l>R[p]||r<L[p])return;
	modify(p<<1,l,r,x);
	modify(p<<1|1,l,r,x);
	pushup(p);
}
ll querymax(int p,int l,int r){
	pushdown(p);
	if(l<=L[p]&&r>=R[p])return mx[p];
	if(l>R[p]||r<L[p])return -1e18;
	return max(querymax(p<<1,l,r),querymax(p<<1|1,l,r));
}
int main(){
	int i,n;
	while(~scanf("%d",&n)){
		for(i=0;i<=(n<<2);i++)lazy[i]=0,mx[i]=0,L[i]=R[i]=0;
		for(i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b),b[i]=a[i].y;
		sort(b+1,b+1+n);
		int cnt=unique(b+1,b+1+n)-b;
		for(i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+cnt,a[i].y)-b+1;
		sort(a+1,a+1+n);
		build(1,1,cnt);
		upd(1,1,0);
		for(i=1;i<=n;i++){
			upd(1,a[i].y,querymax(1,1,a[i].y)+a[i].b);
			modify(1,1,a[i].y-1,a[i].a);
			modify(1,a[i].y+1,cnt,a[i].b);
		}
		printf("%lld\n",mx[1]);
	}
	return 0;
}