Submission #1311732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311732		Lakshya108	Safety (NOI18_safety)	C++20	100 / 100	38 ms	3776 KiB

safety

#include <bits/stdc++.h>
using namespace std;

/*
We maintain the artwork from left to right.

For each stack i:
|final_height[i] - final_height[i-1]| ≤ H

We want to change the original heights S[i]
(minimum add/remove cube operations)
to satisfy the safety condition.
*/

priority_queue<long long> leftHeap; 
// max-heap: represents upper candidates of adjusted heights

priority_queue<long long, vector<long long>, greater<long long>> rightHeap;
// min-heap: represents lower candidates of adjusted heights

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

    int N;
    long long H;
    cin >> N >> H;

    long long x;
    cin >> x; // height of first stack

    /*
    rs = total number of cube operations (add/remove)
    */
    long long rs = 0;

    /*
    Initially, the first stack must stay at height x.
    Both heaps start with x.
    */
    leftHeap.push(x);
    rightHeap.push(x);

    /*
    lo and up track how much the allowed range expands
    as we move to the right.
    Each step allows ±H change.
    */
    long long lo = 0, up = 0;

    for (int i = 1; i < N; i++) {
        lo += H;
        up += H;

        cin >> x; // original height of current stack

        /*
        Case 1:
        Current stack is TOO LOW to be safe.
        We must ADD cubes to raise it.
        */
        if (leftHeap.top() > x + lo) {
            rs += leftHeap.top() - (x + lo);

            leftHeap.push(x + lo);
            rightHeap.push(leftHeap.top() - lo - up);
            leftHeap.push(x + lo);
            leftHeap.pop();
        }

        /*
        Case 2:
        Current stack is TOO HIGH to be safe.
        We must REMOVE cubes.
        */
        else if (rightHeap.top() < x - up) {
            rs += (x - up) - rightHeap.top();

            rightHeap.push(x - up);
            leftHeap.push(rightHeap.top() + lo + up);
            rightHeap.push(x - up);
            rightHeap.pop();
        }

        /*
        Case 3:
        Current stack height is already safe.
        No cube operations needed.
        */
        else {
            leftHeap.push(x + lo);
            rightHeap.push(x - up);
        }
    }

    cout << rs << '\n';
    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