Solution for CodeForces 1313C2 - Skyscrapers (hard version)

Time to learn monotone stack.

Solution #

It’s quite obvious that the answer goes non-decreasing from the start and at some point turns to non-increasing. We want to find the optimal turning point.

We can build two arrays $pre$ and $suf$ of length n. The ith element of $pre$ represents the maximum sum of floors from 1 to i if the floors are non-decreasing. Similar definition for $suf$. The turning point t is where $pre_t+suf_t-m_t$ is maximum.

For example: let $m={1,2,3,2,1}$

We can build the arrays by maintaining a mono-increasing stack stack<pair<ll,ll>> to find the rightest number smaller than m_i. The second element is the number of floors and first element is the number of buildings with the same height. You will understand it better in the detailed buildings process of $pre$:

i=0

nothing in the stack.

pre[0]+=1

Push{1,1} to the stack and now the stack:{{1,1}}

i=1

First set pre[1]=pre[0]

Since m[1]>stack.top().second, no pop.

pre[1]+=m[1]

now $pre_1=3$

Push {1,2} to the stack and the stack is now:{{1,1},{1,2}}

i=2

Similar to i=1.

pre[2]=6

{{1,1},{1,2},{1,3}}

i=3

m[3]<stack.top().second which means that we need to change the height of previous buildings to keep the monotonicity. Keep popping out the bigger element and {1,3} is popped. The pre[3] should be decreased by 1*3 and is 3 now. Then the height of 2,3 should be 2 and pre[3]+=2*2. Finally we push {2,2} to the stack.

i=4

Similarly, we pop out {2,2} and {1,2} and pre[4]-=2*2+1*2 and now pre[4]=1. Then the height of 1,2,3,4 should be 1 and pre[4]+=4*1. Finally push {4,1} to the stack.

We could build $suf$ in the similar way but go from right to left.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define F first
#define S second
 
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<ll> a(n);
	for(auto& it:a) cin>>it;
	vector<ll> pre(n),suf(n);
	stack<pair<ll,ll>> stk;
	forn(i,n){
		int now=1;
		if(i) pre[i]=pre[i-1];
		while(!stk.empty()&&stk.top().S>a[i]){
			now+=stk.top().F;
			pre[i]-=stk.top().F*stk.top().S;
			stk.pop();
		}
		pre[i]+=a[i]*now;
		stk.push({now,a[i]});
	}
	stk=stack<pair<ll,ll>>();
	ford(i,n){
		int now=1;
		if(i!=n-1) suf[i]=suf[i+1];
		while(!stk.empty()&&stk.top().S>a[i]){
			now+=stk.top().F;
			suf[i]-=stk.top().F*stk.top().S;
			stk.pop();
		}
		suf[i]+=a[i]*now;
		stk.push({now,a[i]});
	}
	ll mx=0,pos;
	forn(i,n){
		if(pre[i]+suf[i]-a[i]>mx){
			mx=pre[i]+suf[i]-a[i];
			pos=i;
		}
	}
	for(int i=pos-1;i>=0;i--){
		a[i]=min(a[i+1],a[i]);
	}
	for(int i=pos+1;i<n;i++) a[i]=min(a[i-1],a[i]);
	for(auto it:a) cout<<it<<' ';
	return 0;
}