Submission #965078

#	Time	Username	Problem	Language	Result	Execution time	Memory
965078		12345678	Cat Exercise (JOI23_ho_t4)	C++17	0 / 100	1 ms	4444 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, a[nx], x, y, rt, l[nx], r[nx], dp[nx];
stack<pair<int, int>> s;

void dfs(int u)
{
    if (l[u]) dfs(l[u]), dp[u]=max(dp[u], dp[l[u]]+u-l[u]);
    if (r[u]) dfs(r[u]), dp[u]=max(dp[u], dp[r[u]]+r[u]-u);
    //cout<<"dp "<<u<<' '<<dp[u]<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<n; i++) cin>>x>>y;
    for (int i=1; i<=n; i++)
    {
        if (s.empty()) s.push({a[i], i});
        else
        {
            while (!s.empty()&&s.top().first<a[i])
            {
                l[i]=s.top().second;
                s.pop();
            }           
            if (!s.empty()) r[s.top().second]=i;
            else rt=i;
            s.push({a[i], i});
        }
    }
    //for (int i=1; i<=n; i++) cout<<"debug "<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    dfs(rt);
    cout<<dp[rt];
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26