Submission #944658

#	Time	Username	Problem	Language	Result	Execution time	Memory
944658		12345678	Safety (NOI18_safety)	C++17	100 / 100	47 ms	5592 KiB

safety

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll n, h, x, res, lz;
priority_queue<ll> pql;
priority_queue<ll, vector<ll>, greater<ll>> pqr;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>h;
    for (int i=1; i<=n; i++)
    {
        cin>>x;
        if (pql.empty()||(pql.top()-lz<=x&&x<=pqr.top()+lz)) res+=0;
        else res+=min(abs(x-(pql.top()-lz)), abs(x-(pqr.top()+lz)));
        if (pql.empty()) pql.push(x), pqr.push(x);
        else if (x>=pqr.top()+lz) pqr.push(x-lz), pqr.push(x-lz);
        else pql.push(x+lz), pql.push(x+lz);
        while (pqr.size()>pql.size()) pql.push(pqr.top()+2*lz), pqr.pop();
        while (pql.size()>pqr.size()) pqr.push(pql.top()-2*lz), pql.pop();
        lz+=h;
        /*
        cout<<i<<' '<<res<<' '<<"debug : \n";
        priority_queue<ll> l=pql;
        priority_queue<ll, vector<ll>, greater<ll>> r=pqr;
        cout<<"L : ";
        while (!l.empty()) cout<<l.top()-lz<<' ', l.pop();
        cout<<'\n';
        cout<<"R : ";
        while (!r.empty()) cout<<r.top()+lz<<' ', r.pop();
        cout<<'\n';*/
    }
    cout<<res;
}

• 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