"Weilai Cup" 2022 Niuke summer multi school training camp 2 h.[take the elevator] maintenance section

H.Take the Elevator simulation

Topic analysis

Given $k$ Floor building , Now there is an elevator from $1$ Building departure , At most $m$ people , There is something wrong with the elevator , When running down, you must reach $1$ The building can change its direction . Yes $n$ I hope from $a_i$ The floor arrives $b_i$ floor , Ask how many times the elevator needs to run at least .

set up $ansup[i]$ It means the first $i$ The highest number of floors reached by the wheel ,$ansdown[i]$ It means the first $i$ The highest level of departure , Then the final answer is to enumerate rounds $i$,$ans+=\max (ansup[i],ansdown[i])\ast 2-2$, Get the final answer .

Then it can be divided into two processes , Save all endpoints separately ( Marked ), The number of rounds allocated to each passenger can pass $\lceil \frac{m+cnt}{m}\rceil$ obtain .

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;
}