oj.uz

Submission #965076

# Submission time Handle Problem Language Result Execution time Memory
965076 2024-04-18T05:10:29 Z 12345678 Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 2 ms 2648 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

int n, a[nx], x, y, rt, l[nx], r[nx], dp[nx];
ll res;
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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -