Submission #965080

#	Time	Username	Problem	Language	Result	Execution time	Memory
965080		12345678	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	49 ms	16972 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<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++)
    {
        while (!s.empty()&&a[s.top()]<a[i])
        {
            l[i]=s.top();
            s.pop();
        }           
        if (!s.empty()) r[s.top()]=i;
        else rt=i;
        s.push(i);
    }
    //for (int i=1; i<=n; i++) cout<<"debug "<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    dfs(rt);
    cout<<dp[rt];
}

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