记录编号	608046	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4000.电梯	最终得分	100
用户昵称	我常常追忆未来	是否通过	通过
代码语言	C++	运行时间	1.144 s
提交时间	2025-10-23 09:39:23	内存使用	13.22 MiB

#include <bits/stdc++.h>
#define ls(x) 2*x
#define rs(x) 2*x|1
#define int long long
using namespace std;
const int N=1e6+7;
int st[N],a[N],f[N],t[N],n,top,minn1[4*N],minn2[4*N];
void build1(int p,int l,int r){
	if(l==r){minn1[p]=1e18;return;}
	int mid=l+r>>1;
	build1(ls(p),l,mid),build1(rs(p),mid+1,r);
}
void build2(int p,int l,int r){
	if(l==r){minn2[p]=1e18;return;}
	int mid=l+r>>1;
	build2(ls(p),l,mid),build2(rs(p),mid+1,r);
}
void change1(int p,int l,int r,int x,int val){
	if(l==r){minn1[p]=val;return;} 
	int mid=l+r>>1;
	if(x<=mid) change1(ls(p),l,mid,x,val);
	else change1(rs(p),mid+1,r,x,val);
	minn1[p]=min(minn1[ls(p)],minn1[rs(p)]);
}
int query1(int p,int l,int r,int ql,int qr){
	if(l>qr||r<ql) return 1e18;
	if(ql<=l&&r<=qr) return minn1[p];
	int mid=l+r>>1;
	return min(query1(ls(p),l,mid,ql,qr),query1(rs(p),mid+1,r,ql,qr));
}
void change2(int p,int l,int r,int x,int val){
	if(l==r){minn2[p]=val;return;} 
	int mid=l+r>>1;
	if(x<=mid) change2(ls(p),l,mid,x,val);
	else change2(rs(p),mid+1,r,x,val);
	minn2[p]=min(minn2[ls(p)],minn2[rs(p)]);	
}
int query2(int p,int l,int r,int ql,int qr){
	if(l>qr||r<ql) return 1e18;
	if(ql<=l&&r<=qr) return minn2[p];
	int mid=l+r>>1;
	return min(query2(ls(p),l,mid,ql,qr),query2(rs(p),mid+1,r,ql,qr));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i]>>a[i];
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<=a[i]) top--;
		st[++top]=i;
	}
	build1(1,1,n);
	build2(1,1,n);
	for(int i=1;i<=top;i++) t[i]=t[st[i]],a[i]=a[st[i]];
	n=top,a[n+1]=t[n+1]=0;
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		int l=0,r=i-1;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(f[mid]<=t[i]) l=mid;
			else r=mid-1;
		}
		change1(1,1,n,i,2*a[i]);
		f[i]=min(f[i],t[i]+query1(1,1,n,1,l+1));
		if(l+1<=i-1)f[i]=min(f[i],query2(1,1,n,l+1,i-1));
		change2(1,1,n,i,f[i]+2*a[i+1]);
	}
	cout<<f[n]<<"\n";
	return 0;
}