Submission #164920

#	Time	Username	Problem	Language	Result	Execution time	Memory
164920		gs18103	Safety (NOI18_safety)	C++14	100 / 100	133 ms	45060 KiB

safety

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 303030;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;

struct Node {
    priority_queue <ll> L;
    priority_queue <ll, vector <ll>, greater <ll> > R;
    ll ans = 0, s = 0;
    
    void init(int x) {L.em(x), R.em(x);}
    int size() {return (int)(L.size() + R.size());}
    void merge(Node &X) {
        ans += X.ans;
        while(!X.L.empty()) {
            ll temp = X.L.top() - X.s;
            X.L.pop();
            if(temp >= R.top() + s){
                ans += temp - R.top() - s;
                L.em(R.top() + 2 * s); R.pop();
                R.em(temp - s);
            }
            else L.em(temp + s);
        }
        while(!X.R.empty()) {
            ll temp = X.R.top() + X.s;
            X.R.pop();
            if(temp <= L.top() - s){
                ans += L.top() - temp - s;
                R.em(L.top() - 2 * s); L.pop();
                L.em(temp + s);
            }
            else R.em(temp - s);
        }
    }
} dp[MAX];

int p[MAX], idx[MAX];
ll l[MAX];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    ll h;
    cin >> n >> h;
    for(int i = 1; i <= n; i++) {
        cin >> l[i];
        dp[i].init(l[i]);
        idx[i] = i;
    }
    for(int i = 2; i <= n; i++) {
        p[i] = i - 1;
    }

    for(int i = n; i > 1; i--) {
        dp[idx[i]].s += h;
        if(dp[idx[i]].size() < dp[idx[p[i]]].size()) {
            dp[idx[p[i]]].merge(dp[idx[i]]);
        }
        else {
            dp[idx[i]].merge(dp[idx[p[i]]]);
            idx[p[i]] = idx[i];
        }
    }
    cout << dp[idx[1]].ans;
}

• 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