C++14(g++5.4) 解法, 执行用时: 1461ms, 内存消耗: 31068K, 提交时间: 2019-07-10 16:44:18

#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
using ll=long long;
#define maxn 1000006

int n,m,a[maxn],b[maxn],c[maxn],idx[maxn];
ll bit[maxn];

void add(int x, ll v){
	while(x<=m){
		bit[x]=max(bit[x], v);
		x+=x&-x;
	}
}

ll qry(int x){
	ll ans=0;
	while(x){
		ans=max(ans, bit[x]);
		x-=x&-x;
	}
	return ans;
} 

int main(){
	scanf("%d", &n);
	for(int i=1;i<=n;++i) scanf("%d%d%d", a+i, b+i, c+i);
	memcpy(idx, b+1, sizeof(int)*n);
	sort(idx,idx+n);
	m=unique(idx,idx+n)-idx;
	for(int i=1;i<=n;++i) b[i]=lower_bound(idx,idx+m,b[i])-idx+1;
	for(int i=1;i<=n;++i) idx[i]=i;
	sort(idx+1, idx+n+1, [&](int i, int j){return a[i]!=a[j]?a[i]<a[j]:b[i]<b[j];});
	ll ans=0;
	for(int i=1;i<=n;++i){
		ll x=c[idx[i]]+qry(b[idx[i]]);
		ans=max(ans, x);
		add(b[idx[i]], x);
	}
	printf("%lld\n", ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 982ms, 内存消耗: 52692K, 提交时间: 2020-03-14 17:48:50

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
vector< pair< pair<int,int>,int > > p;

const int maxn=1e6+10;
ll sum[maxn];
ll tmp[maxn];

void update( int x ,ll c ) { while( x<maxn ) sum[x]=max(sum[x],c),x+=lowbit(x); }
ll query( int x ) { ll ans=0; while( x ) ans=max(ans,sum[x]),x-=lowbit(x);return ans; }

int main()
{
	int n;
	scanf("%d",&n);
	for( int i=1;i<=n;i++ )
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		p.push_back( make_pair( make_pair(x,y),z) );
		tmp[i]=y;
	}
	sort(p.begin(),p.end());
	sort(tmp+1,tmp+n+1);
	for( int i=0;i<n;i++ )
	{
		int idx=lower_bound(tmp+1,tmp+1+n,p[i].first.second)-tmp;
		update( idx,query(idx)+p[i].second );
	} 
	printf("%lld\n",query(n));
}