记录编号	608035	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4000.电梯	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.344 s
提交时间	2025-10-22 20:28:01	内存使用	4.36 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1e16+5;
int n;
int a[N],b[N],t[2][N],st[N],tot,f[N];
void build(int p,int l,int r){
	t[1][p]=t[0][p]=inf;
	if(l==r){
		return;
	}
	int mid=((l+r)>>1);
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void solve(int p,int k,int l,int r,int x,int y,int v){
	if(x>y) return;
	if(l==x&&r==y){
		t[p][k]=min(t[p][k],v);
		return;
	}	 
	t[p][k<<1]=min(t[p][k<<1],t[p][k]);
	t[p][k<<1|1]=min(t[p][k<<1|1],t[p][k]);
	int mid=((l+r)>>1);
	if(x>mid){
		solve(p,k<<1|1,mid+1,r,x,y,v);
	}else if(y<=mid){
		solve(p,k<<1,l,mid,x,y,v);
	}else{
		solve(p,k<<1,l,mid,x,mid,v);
		solve(p,k<<1|1,mid+1,r,mid+1,y,v);
	}
	return;
}
int query(int v,int k,int l,int r,int p){
	if(l==r){
		return t[v][k];
	}
	t[v][k<<1]=min(t[v][k<<1],t[v][k]);
	t[v][k<<1|1]=min(t[v][k<<1|1],t[v][k]);
	int mid=((l+r)>>1);
	if(p<=mid){
		return query(v,k<<1,l,mid,p);
	}else{
		return query(v,k<<1|1,mid+1,r,p);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		for(;tot&&b[st[tot]]<=b[i];tot--);
		st[++tot]=i;
	}
	for(int i=1;i<=tot;i++){
		a[i]=a[st[i]];
		b[i]=b[st[i]];
	}
	build(1,1,tot);
	for(int i=0;i<=tot;i++){
		if(i){
			f[i]=min(query(0,1,1,tot,i),query(1,1,1,tot,i)+a[i]);
		}else{
			f[i]=0;
		}
		int res=lower_bound(a+1,a+1+tot,(int)(min(f[i],inf)))-a;
		solve(0,1,1,tot,i+1,res-1,f[i]+2*b[i+1]);
		solve(1,1,1,tot,res,tot,2*b[i+1]);
	}
	cout<<f[tot];
	return 0;
}