比赛 20151028a 评测结果 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
题目名称 有趣的有趣的家庭菜园 最终得分 0
用户昵称 asd 运行时间 1.828 s
代码语言 C++ 内存使用 36.94 MiB
提交时间 2017-06-02 19:51:12
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const int maxn=100007;
int i,j,k,l,n,m;
ll tt,ans;
ll a[maxn],b[maxn],c[maxn],d[maxn],tot;
ll f[maxn],g[maxn];
struct nod {
	ll a,d;
} e[maxn];
struct node {
	ll da,biao,biao1,biao2;
} t[maxn*10];
bool cmp(nod x,nod y) {
	return x.a<y.a;
}
void doing1(int x,ll y) {
	t[x].da=max(t[x].da,y);
	ll u=y-t[x].biao;
	if(t[x].biao2)t[x].biao1=max(t[x].biao1,u);
	else t[x].biao2=1,t[x].biao1=u;
}
void doing2(int x,ll y) {
	t[x].da+=y;
	t[x].biao+=y;
}
void doing(int x) {
	if(t[x].biao2!=0) {
		doing1(x*2,t[x].biao1);
		doing1(x*2+1,t[x].biao1);
		t[x].biao1=t[x].biao2=0;
	}
	if(t[x].biao!=0) {
		doing2(x*2,t[x].biao);
		doing2(x*2+1,t[x].biao);
		t[x].biao=0;
	}
}
void change(int x,int l,int r,int y,int z,ll o) {
	if (y>z) return;
	if (l==y&&r==z) {
		doing2(x,o);
		return;
	}
	int mid=(l+r)/2;
	doing(x);
	if (z<=mid) change(x*2,l,mid,y,z,o);
	else if (y>mid) change(x*2+1,mid+1,r,y,z,o);
	else change(x*2,l,mid,y,mid,o),change(x*2+1,mid+1,r,mid+1,z,o);
	t[x].da=max(t[x*2].da,t[x*2+1].da);
}
void change1(int x,int l,int r,int y,int z,ll o) {
	if (y>z) return;
	if (l==y&&r==z) {
		doing1(x,o);
		return;
	}
	int mid=(l+r)/2;
	doing(x);
	if (z<=mid) change1(x*2,l,mid,y,z,o);
	else if (y>mid) change1(x*2+1,mid+1,r,y,z,o);
	else change1(x*2,l,mid,y,mid,o),change1(x*2+1,mid+1,r,mid+1,z,o);
	t[x].da=max(t[x*2].da,t[x*2+1].da);
}
ll find(int x,int l,int r,int y) {
	if (l==r) return t[x].da;
	int mid=(l+r)/2;
	doing(x);
	if (y<=mid)return find(x*2,l,mid,y);
	else return find(x*2+1,mid+1,r,y);
}
int main() {
	freopen("Fgarden.in","r",stdin);
	freopen("Fgarden.in","w",stdout);
	scanf("%d",&n);
	fo(i,1,n) {
		scanf("%lld%lld%lld",&e[i].a,&b[i],&c[i]);
		e[i].d=i;
	}
	sort(e+1,e+n+1,cmp);
	tot=1;
	a[e[1].d]=tot;
	fo(i,2,n) {
		if(e[i-1].a!=e[i].a)a[e[i].d]=++tot;
		else a[e[i].d]=tot;
	}

	fo(i,1,n) {
		f[i]=b[i]+find(1,1,tot,a[i]);
		change(1,1,tot,1,a[i]-1,-c[i]);
		change1(1,1,tot,a[i],tot,f[i]);
	}
	memset(t,0,sizeof(t));
	fod(i,n,1) {
		g[i]=b[i]+find(1,1,tot,a[i]);
		change(1,1,tot,1,a[i]-1,-c[i]);
		change1(1,1,tot,a[i],tot,g[i]);
	}
	fo(i,1,n) {
		ans=max(ans,f[i]+g[i]-b[i]);
	}
	printf("%lld",ans);
}