"Weilai Cup" 2022 Niuke summer multi school training camp 2H

" Weilai cup "2022 Niuke summer multi school training camp 2 H

---

The question ： Yes $n$ One should take the elevator , from $a$ Sit on the floor until $b$ layer , The full load of the elevator is $m$ people , The total floor is $k$ layer , The elevator can rise from floor to floor , Any layer can choose to descend . But the decline must fall to $1$ The layer can only rise again . The energy consumed by the elevator moving between floors is $1$ , Ask us how much it costs at least to make everyone successfully reach the destination .

---

Ideas ： There are prefixes and algorithmic knowledge prerequisites , Let's first look at the rising personnel , We calculate how many times each floor is passed by the elevator at least , Differential can be used , Finally, merge . For example, if from $3$ Floor to floor $6$ floor , We go through $O(1)$ stay $4$ Floor location $+1$,$7$ Location of building $-1$ that will do . representative $4-6$ The number of times building passed $+1$,$3$ There is no need to add floors because $3$ The first floor does not need to consume elevator energy . At last, the prefix and operation count the minimum number of people passing on all floors , And divide each layer by $m$ Round up , Express Under full load , The elevator Still need How many times have you passed the current floor . And one thing is obvious , If the upper floor passes at least more than the lower floor , Then the lower floor also needs the elevator to pass the same number of times as the upper floor . for example $7$ Layer passes at least $3$ Time , that $7$ The number of elevators passing on floors and below cannot be less than $3$ Time . Finally, you can get the minimum value of the energy spent by the elevator on the rising floor . Next, we will discuss the descending floor , You will find that a large part of the descending floor will repeat with the ascending floor , The process of choosing to descend and then rise again at each rising floor can also make many descending personnel reach the target floor , So we need to be on the same floor Rise and fall Select a maximum number of times .

---

Code ：

/* * @author: Snow * @Description: Algorithm Contest * @LastEditTime: 2022-07-28 19:40:33 */
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb push_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
int n,m,k;
const int N = 2e5+10; 
int suf[N];
int a[N];
int b[N];
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    vector<int>v;
    for(int i=1;i<=n;i++){
    
        cin>>a[i];
        cin>>b[i];
        v.pb(a[i]);
        v.pb(b[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int sum=v.size();
    vector<int>up,down;
    for(int i=1;i<=n;i++){
    
        int l=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        int r=lower_bound(v.begin(),v.end(),b[i])-v.begin();
        if(l<r){
    
            up[l+1]++;
            up[r+1]--;
        }
        else{
    
            down[r+1]++;
            down[l+1]--;
        }
    }  
    for(int i=1;i<=sum;i++){
    
        up[i]+=up[i-1];
        down[i]+=down[i-1];
        int ti1=(up[i]+m-1)/m;
        int ti2=(down[i]+m-1)/m;
        suf[max(ti1,ti2)]=max(suf[max(ti1,ti2)],v[i]-1);
    }
    for(int i=n-1;i>=1;i--)suf[i]=max(suf[i],suf[i+1]);
    int ans=0;
    for(int i=n;i>=1;i--)ans+=suf[i];
    cout<<ans<<endl;
    return 0;
}