fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double 
  5. const long long MOD = 1e9+7;
  6. const long long N = 1e6+9;
  7. ll h[N], Q, n, d[N], R[N];
  8. stack<int>st;
  9.  
  10. void solve(){
  11.     for(int i = n; i >= 1; i--){
  12.         while(!st.empty() && h[st.top()] <= h[i])
  13.             st.pop();
  14.         if(st.empty())
  15.             R[i] = 0;
  16.         else
  17.             R[i] = st.top();
  18.         st.push(i);
  19.     }
  20.     for(int i = n-1; i >= 1; i--){
  21.         if(R[i] != 0)
  22.             d[i] = d[R[i]]+1;
  23.         else 
  24.             d[i] = 0;
  25.     }
  26. }
  27.  
  28. int main()
  29. {
  30.     cin.tie(NULL); cout.tie(NULL);
  31.     ios_base::sync_with_stdio(false);
  32.     //freopen(".inp","r",stdin);
  33.     //freopen(".out","w",stdout);
  34.     cin>>n>>Q;
  35.     for(int i = 1; i <= n; i++)
  36.         cin>>h[i];
  37.     solve();
  38.     ll x;
  39.     while(Q--){
  40.         cin>>x;
  41.         cout<<d[x]<<'\n';
  42.     }
  43. }
Success #stdin #stdout 0.01s 7648KB
comments (?)
stdin
copy 
9 10
9 6 9 6 5 8 10 2 1
1
2
3
4
5
6
7
8
9
10
stdout
copy 
1
2
1
2
2
1
0
0
0
0
https://ideone.com/QimjRT
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!