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