Advertisement
Guest User

Untitled

a guest
Feb 11th, 2021
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     ios_base::sync_with_stdio(0); cin.tie(0);
  7.     int n,ans=0,cur=0;
  8.     cin>>n;
  9.     int a[n],next[n];
  10.     for (int i=0;i<n;++i)
  11.         cin>>a[i];
  12.     stack<int> s;
  13.     for (int i=n-1;i>=0;--i)
  14.     {
  15.         while (!s.empty()&&a[s.top()]<a[i])
  16.             s.pop();
  17.         if (s.empty())
  18.             next[i]=n;
  19.         else
  20.             next[i]=s.top();
  21.         s.push(i);
  22.     }
  23.     while (cur<n)
  24.     {
  25.         ++ans;
  26.         cur=next[cur];
  27.     }
  28.     cout<<ans;
  29.     return 0;
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement