记录编号	446251	评测结果	AAAAAAAAAAA
题目名称	不平凡的boss	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.774 s
提交时间	2017-09-07 20:51:43	内存使用	1.46 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct pt{int x,y,z;}p[N];
bool cmp(pt a,pt b){return a.x>=b.x;}
int n;
typedef pair<int,int> pii;
typedef set<pii>::iterator it;
set<pii> S;
multiset<int> H;
void erase(it l,it x,it r){
    H.erase(H.find(l->first+x->second));
    H.erase(H.find(x->first+r->second));
    H.insert(l->first+r->second);
    S.erase(x);
}
bool test(it x,it y){
    return x->first<=y->first&&x->second<=y->second;
}
bool flag;
void insert(pii v){
    if (S.count(v)) return;
    S.insert(v);
    set<pii>::iterator x=S.find(v),l=x,r=x,ll,rr;
    --l;++r;
    H.erase(H.find(l->first+r->second));
    H.insert(l->first+x->second);
    H.insert(x->first+r->second);
    while (test(l,x)) ll=l,--ll,erase(ll,l,x),l=ll;
    while (test(r,x)) rr=r,++rr,erase(x,r,rr),r=rr;
    if (test(x,l)||test(x,r)) erase(l,x,r);
}
int main()
{
    freopen("playwithboss.in","r",stdin);
    freopen("playwithboss.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    sort(p+1,p+n+1,cmp);
    S.insert(pii(0,1e9));
    S.insert(pii(1e9,0));
    H.insert(0);
    int ans=p[1].x;
    for (int i=1;i<=n;i++){
        flag=(i==17213);
        insert(pii(p[i].y,p[i].z));
        ans=min(ans,p[i+1].x+*H.begin());
    }
    printf("%d\n",ans);
    return 0;
}