Submission #418651

#	Time	Username	Problem	Language	Result	Execution time	Memory
418651		Blagojce	Safety (NOI18_safety)	C++11	100 / 100	118 ms	6980 KiB

safety

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
  
const int mxn = 2e5+5;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1000003;
mt19937 _rand(time(NULL));
clock_t z;
//while((clock()-z)/CLOCKS_PER_SEC > 0.9)
 
 
int n;
ll k;
     
ll a[mxn];/*
struct p{
    ll x, y;
    ll delta;
};
 
vector<p> v1;
vector<p> v2;
 
void Shift(ll h){
    fr(i, 0, (int)v1.size()){
        v1[i].x -= h;
    }
    fr(i, 0, (int)v2.size()){
        v2[i].x += h;
    }
}
 
void Insert(ll h){
    if(h <= v1.back().x){
        fr(i, 0, (int)v2.size()){
            ++v2[i].delta;
        }
         
        fr(i, 0, (int)v1.size()){
            if(h <= v1[i].x){
                ll yh = v1[i].y + abs(v1[i].x - h)*v1[i].delta;
                ll deltah = v1[i].delta+1;
                 
                fr(j, 0, i){
                    ++v1[j].delta;
                }
                fr(j, i, (int)v1.size()){
                    --v1[j].delta;
                }
                 
                p nov = v1.back();
                nov.delta = 1;
                v2.insert(v2.begin(), nov); 
                 
                if(v1.back().delta == 0) v1.pop_back();
                 
                nov.x = h;
                nov.y = yh;
                nov.delta = deltah;
                v1.insert(v1.begin()+i, nov);
                 
                break;
            }
        }
    }
    else if(h >= v2[0].x){
        fr(i, 0, (int)v1.size()){
            ++v1[i].delta;
        }
         
         
        for(int i = (int)v2.size()-1; i >= 0; i --){
            if(h >= v2[i].x){
                ll yh = v2[i].y + abs(v2[i].x-h)*v2[i].delta;
                ll deltah = v2[i].delta+1;
                 
                fr(j, 0, i+1){
                    --v2[j].delta;
                }
                fr(j, i+1, (int)v2.size()){
                    ++v2[j].delta;
                }
                 
                 
                 
                p nov;
                nov.x = h;
                nov.y = yh;
                nov.delta = deltah;
                v2.insert(v2.begin()+i+1, nov);
                 
                 
                nov = v2[0];
                nov.delta = 1;
                v1.pb(nov);
                if(v2[0].delta == 0) v2.erase(v2.begin());
                 
                break;
            }
        }
    }
    else{
        fr(i, 0, (int)v1.size()){
            v1[i].delta ++;
        }
        fr(i, 0, (int)v2.size()){
            v2[i].delta ++;
        }
         
        p nov;
        nov.y = v1.back().y;
        nov.x = h;
        nov.delta = 1;
        v1.pb(nov);
        v2.insert(v2.begin(), nov);
    }
     
     
    fr(i, 0, (int)v1.size()){
        v1[i].y += abs(v1[i].x-h);
    }
    fr(i, 0, (int)v2.size()){
        v2[i].y += abs(v2[i].x-h);
    }
     
}
*/
 
int main(){
    cin >> n >> k;
    fr(i, 0, n){
        cin >> a[i];
    }
     
    pq <ll> v1;
    pq <ll> v2;
    v1.push(a[0]);
    v2.push(-a[0]);
     
    ll ans = 0;
    fr(i, 1, n){
        ll vtop1 = v1.top();
        ll vtop2 = -v2.top();
         
        ll lef = vtop1 - i*k;
        ll rig = vtop2 + i*k;
        if(a[i] < lef){
            ans += abs(lef-a[i]);
            v1.push(a[i]+i*k);
            v1.push(a[i]+i*k);
            v1.pop();
            v2.push(-(lef-i*k));
        }
        else if(a[i] > rig){
            ans += abs(rig-a[i]);
            v2.push(-(a[i]-i*k));
            v2.push(-(a[i]-i*k));
            v2.pop();
            v1.push(rig+i*k);
        }
        else{
            v1.push(a[i]+i*k);
            v2.push(-(a[i]-i*k));
        }
     
    }
    cout<<ans<<endl;
     
    /*
     
    p nov;
    nov.x = a[0];
    nov.y = 0;
    nov.delta = 1;
    v1.pb(nov);
    v2.pb(nov);
    fr(i, 1, n){
        Shift(k);
        Insert(a[i]);
    }
    cout<<v1.back().y<<endl;*/
     
 
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29