1313C2 - Skyscrapers (hard version)

 Problem Link

Algorithm: constructive algorithms, nearest smallest element

In this problem we need to find the smallest number of reductions made to numbers in the array such that at the end there is no local minimum present in the array (and the two numbers that are larger than the local minimum need not be adjacent to it).

Notice how the "shape" of the numbers in the answer is always a peak: there is a sequence of non-decreasing numbers followed by a sequence of non-increasing numbers. We can treat every number in the array as the apex and then calculate the number of reductions required for this apex.

Let's only look at the left side of the apex (since the logic is the same for the right side too): From the apex the numbers can only decrease and then reach it's lowest point. We would like to allow the numbers to decrease as slowly as possible so that the sum is maximal. Because of this, we always choose the nearest number to the left of the apex that is smaller than it, then the next nearest number to the left of that number that is smaller and so on and so forth. 

Once we know the index and the value of the nearest smallest elements on either side of our apex, we can calculate the sum of the values on the left of the apex and on the right of the apex. The sum on the left will be the sum of the values on the left of the nearest smallest element on the left + the number of numbers in between the left nearest smallest element and the apex * value of apex. The same goes for the values on the right.

Finally, whichever apex yields the largest sum must be the answer. We find the maximum and output the adjusted heights of the towers

Code:

#include <iostream>

#include <vector>

#include <algorithm>

#include <stack>

using namespace std;

using ll = long long;

int main() {

    int n;

    cin >> n;

    vector <ll> nums(n+2), l(n+2), r(n+2);

    for (int i = 1; i <= n; i++)

        cin >> nums[i];

    stack <int> s;

    s.push(0);

    for (int i = 1; i <= n; i++) {

        while (nums[s.top()] > nums[i])

            s.pop();

        l[i] = l[s.top()] + (ll)(i - s.top()) * nums[i];

        s.push(i);

    }

    while (!s.empty())

        s.pop();

    s.push(n+1);

    for (int i = n; i >= 1; i--) {

        while (nums[s.top()] > nums[i])

            s.pop();

        r[i] = r[s.top()] + (ll)(s.top() - i) * nums[i];

        s.push(i);

    }

    int id = 0;

    ll sum = 0;

    for (int i = 1; i <= n; i++) {

        if (l[i] + r[i] - nums[i] > sum) {

            sum = l[i] + r[i] - nums[i];

            id = i;

        }

    }

    vector <ll> ans(n+2);

    ans[id] = nums[id];

    for (int i = id-1; i >= 1; i--) {

        ans[i] = min(ans[i+1], nums[i]);

    }

    for (int i = id+1; i <= n; i++) {

        ans[i] = min(ans[i-1], nums[i]);

    }

    for (int i = 1; i <= n; i++)

        cout << ans[i] << ' ';

    cout << '\n';

}