Submission #60589991

---

Source Code Expand

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int LOG = 19;
const int N = 1 << LOG;

/**
 * Description: Sparse table for minimum on the range $[l, r), l < r$.
 * You can push back an element in $O(\text{LOG})$ and query anytime.
 */

struct SparseTable
{
	vector<PII> t[LOG];
	
	void push_back(PII v)
	{
		int i = SZ(t[0]);
		t[0].PB(v);
		FOR (j, 0, LOG - 1) 
			t[j + 1].PB(max(t[j][i], t[j][max(0, i - (1 << j))]));
	}
	// [l, r)
	PII query(int l, int r)
	{
		assert(l < r && r <= SZ(t[0]));
		int i = 31 - __builtin_clz(r - l);
		return max(t[i][r - 1], t[i][l + (1 << i) - 1]);
	}
} st;

int n;
int a[N];
LL pref[N];
LL ans[N];

void solve(int l, int r)
{
	if (l > r)
		return;
	auto [mx, lastPos] = st.query(l, r + 1);
	VI poses = {lastPos};
	while (poses.back() > l)
	{
		auto [val, pos] = st.query(l, poses.back());
		assert(val <= mx);
		if (val < mx)
			break;
		poses.PB(pos);
	}
	reverse(ALL(poses));
	LL s = pref[r + 1] - pref[l];
	int prv = l - 1;
	for (int i : poses)
	{
		if ((i > 0 && a[i - 1] < a[i]) || (i + 1 < n && a[i + 1] < a[i]))
		{
			if (l > 0 && a[l - 1] < s)
				ans[i] = ans[l - 1];
			else if (r + 1 < n && a[r + 1] < s)
				ans[i] = ans[r + 1];
			else
				ans[i] = s;
		}
		else
		{
			ans[i] = a[i];
		}
		solve(prv + 1, i - 1);
		prv = i;
	}
	solve(prv + 1, r);
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> a[i];
		st.PB({a[i], i});
	}
	FOR(i, 0, n)
		pref[i + 1] = pref[i] + a[i];
	solve(0, n - 1);
	FOR(i, 0, n)
		cout << ans[i] << " ";
	cout << "\n";
	return 0;
}

Submission Info

Judge Result