Advertisement
hkshakib

Untitled

Jun 10th, 2020
1,063
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int n;
  6.     cin>>n;
  7.     int arr[n+1];
  8.     for(int i=1; i<=n; i++)
  9.         cin>>arr[i];
  10.  
  11.     stack <pair<int,int>> s;
  12.     vector<pair<int,int>>vec;
  13.     s.push({1,arr[1]});
  14.     for (int i = 2; i <= n; i++)
  15.     {
  16.  
  17.         if (s.empty())
  18.         {
  19.             s.push({i,arr[i]});
  20.             continue;
  21.         }
  22.         while (s.empty() == false && s.top().second < arr[i])
  23.         {
  24.             vec.push_back({s.top().first,i});
  25.             s.pop();
  26.         }
  27.         s.push({i,arr[i]});
  28.     }
  29.     while (s.empty() == false)
  30.     {
  31.         vec.push_back({s.top().first,-1});
  32.         s.pop();
  33.     }
  34.     sort(vec.begin(),vec.end());
  35.     for(int i=0;i<vec.size();i++)
  36.     {
  37.         if(vec[i].second==-1)
  38.             cout<<-1<<" ";
  39.         else cout<<(vec[i].second-vec[i].first)<<" ";
  40.     }
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement