Submission #1311731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311731		Lakshya108	Safety (NOI18_safety)	C++20	3 / 100	23 ms	3168 KiB

safety

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

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

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

    vector<long long> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    /*
        We maintain a valid interval [low, high] for the current stack height.
        Initially, for the first stack, it must be exactly S[0].
    */

    long long low = 0, high = 0;

    /*
        Two heaps are used:
        - leftHeap  : max-heap, stores candidates near the upper side
        - rightHeap : min-heap, stores candidates near the lower side

        Together they help us "pull" heights back into the allowed interval
        with minimum number of cube add/remove operations.
    */
    priority_queue<long long> leftHeap;
    priority_queue<long long, vector<long long>, greater<long long>> rightHeap;

    // Total number of operations (adding/removing cubes)
    long long operations = 0;

    // Initialize using the first stack
    leftHeap.push(S[0]);
    rightHeap.push(S[0]);

    for (int i = 1; i < N; i++) {
        /*
            When moving from stack i-1 to i,
            the allowed height range expands by H on both sides.
        */
        low += H;
        high += H;

        long long currentHeight = S[i];

        /*
            Case 1:
            Current stack is TOO LOW to satisfy |S[i] - S[i-1]| ≤ H
            → we must ADD cubes
        */
        if (leftHeap.top() > currentHeight + low) {
            long long required = leftHeap.top() - (currentHeight + low);
            operations += required;

            // Adjust heaps to reflect the forced increase
            leftHeap.push(currentHeight + low);
            rightHeap.push(leftHeap.top() - low - high);
            leftHeap.pop();
        }

        /*
            Case 2:
            Current stack is TOO HIGH
            → we must REMOVE cubes
        */
        else if (rightHeap.top() < currentHeight - high) {
            long long required = (currentHeight - high) - rightHeap.top();
            operations += required;

            // Adjust heaps to reflect the forced decrease
            rightHeap.push(currentHeight - high);
            leftHeap.push(rightHeap.top() + low + high);
            rightHeap.pop();
        }

        /*
            Case 3:
            Current stack already lies in the safe interval
            → no operations needed
        */
        else {
            leftHeap.push(currentHeight + low);
            rightHeap.push(currentHeight - high);
        }
    }

    cout << operations << "\n";
    return 0;
}

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