Submission #746228

#	Time	Username	Problem	Language	Result	Execution time	Memory
746228		Seb	Safety (NOI18_safety)	C++17	100 / 100	78 ms	5476 KiB

safety

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct F{
    ll m,b,izq,der;
    priority_queue <ll> pq1;
    priority_queue <ll,vector<ll>,greater<ll>> pq2;
    F(ll M, ll B, vector <ll> V) {
        m = M;
        b = B;
        izq = 0;
        der = 0;
        if (!V.empty()) {
            pq1.push(V[0]);
            pq2.push(V[1]);
        }
    }
    void unir(F a) {
        m += a.m;
        b += a.b;
        if (pq1.top()+izq >= a.pq1.top()) {
            while (!a.pq1.empty()) {
                pq1.push(a.pq1.top()-izq);
                a.pq1.pop();
            }
            while (!a.pq2.empty()) {
                pq1.push(a.pq2.top()-izq);
                a.pq2.pop();
            }
        }
        else if (pq2.top()+der <= a.pq2.top()) {
            while (!a.pq1.empty()) {
                pq2.push(a.pq1.top()-der);
                a.pq1.pop();
            }
            while (!a.pq2.empty()) {
                pq2.push(a.pq2.top()-der);
                a.pq2.pop();
            }
        }
        else {
            while (!a.pq1.empty()) {
                pq1.push(a.pq1.top()-izq);
                a.pq1.pop();
            }
            while (!a.pq2.empty()) {
                pq2.push(a.pq2.top()-der);
                a.pq2.pop();
            }
        }
        return;
    }
    void act(ll h) {
        if (m==1) {
            m--;
            b += (pq1.top()+izq);
            pq2.push(pq1.top()+izq-der);
            pq1.pop();
        }
        else if (m==-1) {
            m++;
            b -= (pq2.top()+der);
            pq1.push(pq2.top()+der-izq);
            pq2.pop();
        }
        izq -= h;
        der += h;
        return;
    }
};

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,h,aux;
cin>>n>>h;
F f = F(0,0,{});
for (int i=0;i<n;i++) {
    cin>>aux;
    if (!f.pq1.empty() && !f.pq2.empty()) {
        if (f.pq1.top()+f.izq >= aux) f.unir(F(1,-aux,{aux,aux}));
        else if (f.pq2.top()+f.der <= aux) f.unir(F(-1,aux,{aux,aux}));
        else f.unir(F(0,0,{aux,aux}));
    }
    else f = F(0,0,{aux,aux});
    f.act(h);
}
cout<<f.b;
return 0;
}

• 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