Submission #1055420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055420		YassirSalama	Financial Report (JOI21_financial)	C++17	12 / 100	99 ms	29008 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
const int maxn=3e5+100;
vector<int> v[maxn];
int depth[maxn];
void dfs(int node,int par){
    depth[node]=depth[par]+1;
    for(auto x:v[node]){
        dfs(x,node);
    }
}
signed main(){
    int n,d;
    cin>>n>>d;
    stack<pair<int,int>> st;
    int nge[n];for(int i=0;i<n;i++) nge[i]=n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(!st.empty()&&st.top().F<x){
            nge[st.top().S]=i;
            st.pop();
        }
        st.push({x,i});
    }
    for(int i=0;i<n;i++){
        v[nge[i]].push_back(i);
    }
    depth[n]=-1;
    dfs(n,n);
    int ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,depth[i]);
    }
    cout<<ans<<endl;

}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 12 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35