“蔚来杯“2022牛客暑期多校训练营2 H.[Take the Elevator] 维护线段

H.​​Take the Elevator​​ 模拟

题目分析

给定层楼的楼栋，现在有一个电梯从楼出发，最多承载人，电梯有故障，向下运行时必须到达楼方可改变方向。有个人希望从楼层到达楼层，问电梯至少需要跑多少趟。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

struct node{ int s, t; }up[N], down[N];

int ansup[N], ansdown[N];

inline void solve(){
    int n = 0, m = 0, k = 0; cin >> n >> m >> k;
    int upcnt = 0, downcnt = 0;
    for(int i = 1; i <= n; i++){
        int a, b; cin >> a >> b;
        if(a < b) up[++upcnt] = node{.s = a, .t = 1}, up[++upcnt] = node{.s = b, .t = -1};
        else down[++downcnt] = node{.s = a, .t = -1}, down[++downcnt] = node{.s = b, .t = 1};
    }
    int upans = 0, downans = 0;
    sort(up + 1, up + 1 + upcnt, [](const node &x, const node &y){ return x.s < y.s || x.s == y.s && x.t < y.t; });
    sort(down + 1, down + 1 + downcnt, [](const node &x, const node &y){ return x.s < y.s || x.s == y.s && x.t < y.t; });
    int now = 0; 
    for(int i = 1; i <= upcnt; i++){
        if(up[i].t == -1)
            ansup[(now + m - 1) / m] = up[i].s;    
        now += up[i].t;
    }
    assert(now == 0);
    for(int i = 1; i <= downcnt; i++){
        if(down[i].t == -1)
            ansdown[(now + m - 1) / m] = down[i].s;
        now += down[i].t;
    }
    int ans = 0;
    for(int i = 1; i <= 200000; i++)
        ans += 2 * max({1ll, ansup[i], ansdown[i]}) - 2;
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}