记录编号	608021	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4000.电梯	最终得分	100
用户昵称	梦那边的美好ME	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2025-10-22 17:22:46	内存使用	4.50 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n;
ll t[110000],a[110000];
ll f[110000];
ll st[110000],top;
ll b[410000],d[410000];

void build(ll o,ll l,ll r){
	if (l==r){
		b[o]=d[o]=1e18;
		return;
	}
	ll mid=(l+r)/2;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
}

ll query(ll f[],ll o,ll l,ll r,ll la,ll ra){
	if (l==r){
		return f[o];
	}
	ll mid=(l+r)/2;
	ll ans=1e18;
	if (la<=mid){
		ans=min(ans,query(f,o*2,l,mid,la,ra));
	}
	if (mid<ra){
		ans=min(ans,query(f,o*2+1,mid+1,r,la,ra));
	}
	return ans;
}

void update(ll f[],ll o,ll l,ll r,ll x,ll v){
	if (l==r){
		f[o]=v;
		return;
	}
	ll mid=(l+r)/2;
	if (x<=mid) update(f,o*2,l,mid,x,v);
	else update(f,o*2+1,mid+1,r,x,v);
	f[o]=min(f[o*2],f[o*2+1]);
}

int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld %lld",&t[i],&a[i]);
		while (top&&a[st[top]]<=a[i]) --top;
		st[++top]=i;
	}
	for (int i=1;i<=top;i++){
		t[i]=t[st[i]];
		a[i]=a[st[i]];
	}
	n=top;
	t[n+1]=0;
	a[n+1]=0;
	build(1,1,n);
	for (int i=1;i<=n;i++) f[i]=1e18;
	f[0]=0;
	for (int i=1;i<=n;i++){
		ll l=0,r=i-1;
		while (l<r){
			ll mid=(l+r+1)/2;
			if (f[mid]<=t[i]) l=mid;
			else r=mid-1;
		}
		update(b,1,1,n,i,2*a[i]);
		f[i]=min(f[i],t[i]+query(b,1,1,n,1,l+1));
		if (l+2<=i) f[i]=min(f[i],query(d,1,1,n,l+1,i-1));
		update(d,1,1,n,i,f[i]+2*a[i+1]);
	}
	printf("%lld",f[n]);
	return 0;
}