记录编号	608019	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4000.电梯	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.348 s
提交时间	2025-10-22 15:37:38	内存使用	4.38 MiB

#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define INF 1e18
const int MAXN = 1e5 + 5;

int n, cnt, st[MAXN], top;
ll t1[MAXN], a1[MAXN];
ll t[MAXN], a[MAXN];
ll f[MAXN];

struct Tree{
    int l, r;
    ll minx[2];
}tr[MAXN << 2];

void pushup(int p){
    tr[p].minx[0] = min(tr[ls].minx[0], tr[rs].minx[0]);
    tr[p].minx[1] = min(tr[ls].minx[1], tr[rs].minx[1]);
}

void build(int p, int l, int r){
    tr[p].l = l, tr[p].r = r;
    tr[p].minx[0] = tr[p].minx[1] = INF;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void change(int p, int pos, ll val, int o){
    if(tr[p].l == tr[p].r){
        tr[p].minx[o] = val;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(pos <= mid) change(ls, pos, val, o);
    else change(rs, pos, val, o);
    pushup(p);
}

ll query(int p, int L, int R, int o){
    if(tr[p].r < L || tr[p].l > R) return INF;
    if(L <= tr[p].l && tr[p].r <= R) return tr[p].minx[o];
    return min(query(ls, L, R, o), query(rs, L, R, o));
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> t1[i] >> a1[i];
    for(int i = 1;i <= n;i ++){
        while (top && a1[st[top]] <= a1[i]) top--;
        st[++top] = i;
    }
    cnt = top;
    for(int i = 1; i <= cnt;i ++){
        t[i] = t1[st[i]];
        a[i] = a1[st[i]];
    }
    a[cnt + 1] = 0;
    fill(f + 1, f + cnt + 1, INF);
    f[0] = 0;
    if(cnt > 1) build(1, 1, cnt - 1);
    for(int i = 1;i <= cnt;i ++){
        ll res = INF;
        res = min(res, max(f[0], t[i]) + 2 * a[1]);
        int l = 1, r = i - 1, p = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            if (f[mid] <= t[i]) p = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(cnt > 1 && 1 <= p) res = min(res, t[i] + query(1, 1, p, 0));
        if(cnt > 1 && p + 1 <= i - 1) res = min(res, query(1, p + 1, i - 1, 1));
        f[i] = res;
        if(i < cnt){
            change(1, i, 2 * a[i + 1], 0);
            change(1, i, f[i] + 2 * a[i + 1], 1);
        }
    }
    cout << f[cnt] << '\n';
    return 0;
}