记录编号	206336	评测结果	AAAAAAAAAAA
题目名称	不平凡的boss	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	0.618 s
提交时间	2015-11-06 19:15:37	内存使用	2.32 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>

template<class Num>void read(Num &x)
{
	int flag = 1;
	char c;
	while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')
		x *= 10, x += c - '0';
	x *= flag;			
}
template<class Num>void write(Num &x)
{
	static int s[25];
	int sl = 0;
	
	if(!x) putchar('0');
	if(x < 0) putchar('-'), x *= -1;
	while(x) s[sl++] = x % 10, x /= 10;
	while(sl--) putchar(s[sl] + '0');
}

const int maxn = 1e5 + 20, inf = 0x3f3f3f3f;
typedef std::pair<int,int> Node;
typedef std::pair<int,std::pair<int,int> > HeapNode;
#define X first
#define Y second
std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode> > heap;

int N;
std::pair<int,Node> M[maxn];
std::set<int> S;
int v[maxn], w[maxn];
bool flag[maxn];

bool cmp(const std::pair<int,Node> &A,const std::pair<int,Node> &B)
{
	return A.Y < B.Y;
}
void init()
{
	int a, b, c;
	
	read(N);
	for(int i = 1; i <= N; i++)
	{
		read(a), read(b), read(c);
		M[i] = std::make_pair(c, std::make_pair(a, b));
	}
	
	std::sort(M + 1, M + N + 1, cmp);
	
	for(int i = 1; i <= N; i++)
		w[i] = M[i].Y.X, M[i].Y.X = i;
}
int getpre(std::set<int>::iterator T)
{
	return T == S.begin() ? -1 : *(--T);	
}
int getsur(std::set<int>::iterator T)
{
	return (++T) == S.end() ? -1 : *T;
}
void insert(int pos,int val)
{
	int G;
	
	v[pos] = val;
	std::set<int>::iterator P = S.insert(pos).first;
	flag[pos] = true;
	
	G = getsur(P);
	if(G != -1 && v[pos] <= v[G])
	{
		flag[pos] = false;
		S.erase(P);
		return;
	}
	
	G = getpre(P);
	while(G != -1 && v[pos] >= v[G])
	{
		flag[G] = false;
		S.erase(S.find(G));
		G = getpre(P);
	}
	
	int l = getpre(P), r = getsur(P);

	if(l != -1) heap.push(std::make_pair(w[l] + v[pos], std::make_pair(l, pos)));
	if(r != -1) heap.push(std::make_pair(w[pos] + v[r], std::make_pair(pos, r)));
	
//	std::cerr << pos << ' ' << heap.size() << ' ' << (heap.empty() ? inf : heap.top().X) << std::endl;
}
int GetMin()
{
	while(true)
	{
		HeapNode t = heap.top();
		
		if(flag[t.Y.X] && flag[t.Y.Y] && getsur(S.find(t.Y.X)) == t.Y.Y)
			return t.X;
		else 
			heap.pop();
	}
}
void solve()
{
	int Ans = inf;
	
	std::sort(M + 1, M + N + 1);
		
	Ans = M[N].X;
	
	insert(0, inf), insert(N + 1, 0);
	
	for(int i = N; i >= 1; i--)
	{
		insert(M[i].Y.X, M[i].Y.Y);
		Ans = std::min(Ans, M[i - 1].X + GetMin());
	}
	
	write(Ans);
}
int main()
{
	freopen("playwithboss.in","r",stdin);
	freopen("playwithboss.out","w",stdout);
	
	init();
	
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}