fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimization ("O3")
  5. #pragma GCC optimization ("unroll-loops")
  6. #define all(x) x.begin(),x.end()
  7. #define ll long long int
  8. const int MAX = 1e6+7;
  9. const int MOD = 998244353;
  10.  
  11. vector<int> solve(vector<int> &a,vector<int> &r,int f)
  12. {
  13.   int n = a.size();
  14.   unordered_map<int,queue<int> > pq;
  15.   stack<pair<int,int> > st;
  16.   pq.clear();
  17.  
  18.   for(int i = n-1;i>=0;i--)
  19.   {
  20.       int jj = i;
  21.       if(f) jj = n-1-i;
  22.  
  23.       int val = a[i];
  24.       if(pq[val].size() == 0) pq[val].push(i);
  25.       else
  26.       {
  27.         int index = -1;
  28.         while(!st.empty() && st.top().first<=val) st.pop();
  29.         if(!st.empty()) index = st.top().second;	
  30.  
  31.         if(index !=-1)    
  32.         {
  33.           while(pq[val].size() && pq[val].front()>index) pq[val].pop();
  34.         }
  35.         r[jj]+=pq[val].size();
  36.         pq[val].push(i); 
  37.       }
  38.       st.push(make_pair(val,i));
  39.   }
  40.   return r;
  41. }
  42.  
  43.  
  44. int main(int argc, char const *argv[])
  45. {
  46.  
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(0); cout.tie(0);
  49.  
  50.     int t; cin>>t;
  51.     while(t-->0)
  52.     {
  53.       int n; cin>>n;
  54.       vector<int> l(n,0),r(n,0),a(n);
  55.       for(int i = 0;i<n;i++) cin>>a[i];
  56.  
  57.       l = solve(a,l,0);
  58.       reverse(all(a));
  59.       r = solve(a,r,1);
  60.  
  61.       for(int i = 0;i<n;i++) cout<<l[i]+r[i]<<" ";
  62.       cout<<'\n';
  63.  
  64.     }
  65.  
  66.   return 0;
  67. }
Success #stdin #stdout 0s 4916KB
comments (?)
stdin
copy 
1
5
1 2 2 3 2
stdout
copy 
0 1 1 0 0
https://ideone.com/VqKYqk
language:
C++14 (gcc 8.3)
created:
3 years 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!