Advertisement
tungSfer

Untitled

May 15th, 2021
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el endl
  5. #define umi unordered_map<int, int>
  6. #define umll unordered_map<ll, ll>
  7. #define all(vect) vect.begin(), vect.end()
  8. #define reset(A) memset(A, 0, sizeof(A))
  9.  
  10. const int mod = 1e9 + 7;
  11.  
  12. using namespace std;
  13.  
  14. void solve()
  15. {
  16.     int n;
  17.     cin >> n;
  18.     int a[n + 5];
  19.     stack<int> st;
  20.     umi mp;
  21.     for(int i = 0; i < n; i++)
  22.     {
  23.         cin >> a[i];
  24.         mp[i]++;
  25.     }
  26.     st.push(0);
  27.     for(int i = 1; i < n; i++)
  28.     {
  29.         while(a[i] >= a[st.top()] && !st.empty())
  30.         {
  31.             mp[i] += mp[st.top()];
  32.             st.pop();
  33.         }
  34.         st.push(i);
  35.     }
  36.     for(int i = 0; i < n; i++)
  37.     {
  38.         cout << mp[i]<< " ";
  39.     }
  40.     cout << el;
  41. }
  42.  
  43. int main()
  44. {
  45.     int t = 1;
  46.     cin >> t;
  47. //  cin.ignore();
  48.     while(t--)
  49.     {
  50.         solve();
  51.     }
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement