Submission #71499193

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO {
	template<typename T> inline void read(T &x) {
		bool f = 1;
		x = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-')f = 0;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
		x = f ? x : -x;
	}
	template<typename T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(('0' + x % 10));
	}
	template <typename T, typename ...Args> inline
	void read(T &x, Args &...args) {read(x),read(args...);}
	template<typename T> inline void write(T x, char c) {write(x), putchar(c);}
}
using namespace IO;
const int INF=1e18;

int n;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	cin>>n;
	vector<int> s(n+1);
    for(int i=1;i<=n;i++) cin>>s[i];
    vector<int> l(n+1),r(n+1),f(n+1),ff;
    for(int i=1;i<=n;i++)
	{
        int x=0;
        while(!ff.empty()&&s[ff.back()]<s[i]){x=ff.back();ff.pop_back();}
        if(!ff.empty()) r[ff.back()]=i,f[i]=ff.back();
        if(x) l[i]=x,f[x]=i;
        ff.push_back(i);
    }
    
    int ans=1;
    for(int i=1;i<=n;i++)
		if(f[i]==0)
		{
			ans=i;
			break;
		}
    vector<vector<int> > sum(n+1);
    for(int i=1;i<=n;i++)
	{
        if(l[i]) sum[i].push_back(l[i]);
        if(r[i]) sum[i].push_back(r[i]);
    }
    vector<int> fff;
	vector<int> ss;
	ss.push_back(ans);
    while(!ss.empty())
	{
		int u=ss.back();
		ss.pop_back();
		fff.push_back(u);
		for(int v:sum[u]) ss.push_back(v);
	}
    vector<int> Ans(n+1);
    for(int i=fff.size()-1;i>=0;i--)
	{
        int u=fff[i],x=0;
        for(int v:sum[u]) x=max(x,Ans[v]+llabs(u-v));
        Ans[u]=x;
    }
    cout<<Ans[ans]<<"\n";

	return 0;
}

Submission Info

Judge Result