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

#include <iostream>
#include <cstdio>
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,stk[N],top;
ll mx[N<<2],f[N],T[N],a[N];
void pushup(int p){mx[p]=min(mx[ls],mx[rs]);}
void upd(int p,int l,int r,int x,ll v){
	if(l==r)return mx[p]=v,void();
	int mid=(l+r)>>1;
	if(x<=mid)upd(ls,l,mid,x,v);
	if(x>mid)upd(rs,mid+1,r,x,v);
	pushup(p);
}
ll qry(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R)return mx[p];
	int mid=(l+r)>>1;ll cnt=1e15;
	if(L<=mid)cnt=min(cnt,qry(ls,l,mid,L,R));
	if(R>mid)cnt=min(cnt,qry(rs,mid+1,r,L,R));
	return cnt;
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout); 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld %lld",T+i,a+i);
	for(int i=1;i<=n;i++){
		while(top&&a[stk[top]]<=a[i])top--;
		stk[++top]=i; 
	}
	n=top;
	for(int i=1;i<=n;i++){
		a[i]=a[stk[i]];
		T[i]=T[stk[i]];
	}
	int L,R,mid;
	for(int i=1;i<=n;i++){
		L=0,R=i-1;
		while(L<R){
			mid=(L+R+1)>>1;
			if(f[mid]<=T[i])L=mid;
			else R=mid-1;
		}
		f[i]=T[i]+2*a[L+1];
		if(L+1<=i-1)f[i]=min(f[i],qry(1,1,n,L+1,i-1));
		upd(1,1,n,i,f[i]+2*a[i+1]);
	}
	printf("%lld\n",f[n]);
	return 0;
}