#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n;
struct node {
int a,b,sum;
bool operator <(const node bb) const {
return b < bb.b;
}
} a[N];
struct kkk {
int num, ad;
};
struct xds_tree {
kkk tree[N << 2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
void pushup(int x) {
if(tree[ls].ad <= tree[rs].ad) return void(tree[x] = tree[ls]);
return void(tree[x] = tree[rs]);
}
void build(int x,int l,int r) {
if(l==r) return void(tree[x].ad = a[l].sum),void(tree[x].num = l);
build(ls,l,mid), build(rs,mid+1,r);
return void(pushup(x));
}
void update(int x,int l,int r,int L,int d) {
if(l==r && r==L) return void(tree[x].ad = d);
if(L<=mid) update(ls,l,mid,L,d);
else update(rs,mid+1,r,L,d);
return void(pushup(x));
}
kkk query(int x,int l,int r,int L,int R) {
if(l>=L&&r<=R) return tree[x];
kkk res = {0,1e12};
if(L<=mid) res = query(ls,l,mid,L,R);
if(R>mid) {
kkk p = query(rs,mid+1,r,L,R);
if(p.ad < res.ad) res = p;
}
return res;
}
} T;
signed main() {
// freopen("boast.in","r",stdin);
// freopen("boast.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n; ++i) {
cin>>a[i].a>>a[i].b;
a[i].sum = a[i].a + a[i].b;
}
sort(a+1,a+1+n);
T.build(1,1,n);
int sum = 0, ans = 1e12;
for(int i=1; i<n-1; ++i) {
sum = a[i].a;
kkk q = T.query(1,1,n,i+1,n);
sum += q.ad;
T.update(1,1,n,q.num,INT_MAX);
sum += T.query(1,1,n,i+1,n).ad;
T.update(1,1,n,q.num,q.ad);
ans = min(ans,sum);
}
cout<<ans<<"\n";
return 0;
}
这段代码在-O2 -std=c++14 环境下,会CE,但是dev-c++编译错误但是继续运行(能过大样例),这是为什么。