Envío 4940

Código

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
char el = '\n';
char esp = ' ';

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ostream& operator<<(ostream& os, const vector<ll> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

const ll oo=1e15;

struct rango{
    ll left, rigth, dis, disp, resta; 
    rango(){}
    rango(ll left, ll rigth, ll dis, ll disp, ll resta) : left(left), rigth(rigth), dis(dis), disp(disp), resta(resta){}
};

int main(){
    fast_io;
    /*
     freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    int arboles, personas;
    cin>>arboles>>personas;
    
    vl trees(arboles);
    
    for(int i=0;i<arboles;i++){
        cin>>trees[i];
    }
    sort(trees.begin(), trees.end());
    
    int ids=0;
    map<int,rango> m;
    
    m[ids++] = {oo, trees[0] - 1, 1, oo, 1};
    
    for(int i=0;i + 1<arboles;i++){
        ll dif= trees[i + 1] - trees[i] - 1;
        if(dif){
            m[ids++] = {trees[i] + 1, trees[i + 1] - 1, 1, dif, 2};
        }
    }
    m[ids++] = {trees.back() + 1, oo, 1,oo,1};
    
    ll ans=0;
    
    vl anss;
    
    auto it=m.begin();
    
    while(personas){
        it = m.begin();
        
        while(it != m.end() && personas){
            rango &cur_r = it->ss;
            //Uso distancia actual;
            if(cur_r.left == oo){
                anss.pb(cur_r.rigth);
                cur_r.rigth--;
                ans += cur_r.dis;
                cur_r.dis++;
                personas--;
            }else if(cur_r.rigth == oo){
                anss.pb(cur_r.left);
                cur_r.left++;
                ans += cur_r.dis;
                cur_r.dis++;
                personas--;
            }else{
                anss.pb(cur_r.left);
                cur_r.left++;
                ans += cur_r.dis;
                cur_r.disp--;
                personas--;
                if(cur_r.disp){
                    anss.pb(cur_r.rigth);
                    cur_r.rigth--;
                    ans += cur_r.dis;
                    cur_r.disp--;
                    personas--;
                }
                cur_r.dis++;
            }
            if(cur_r.disp == 0){
                it = m.erase(it);
            }else{
                it++;
            }
        }
        
    }
    
    cout<<ans<<el;
    cout<<anss;
}

/*

*/