fork(1) download
copy 
  1. /*
  2. * author : lx_lovin
  3. */#include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. vector<int> solve (vector<int> S,int n) {
  7.     int m = S[n-1];
  8.     int Sp[n];
  9.     Sp[n-1] = m;
  10.     for(int i=n-2;i>=0;i--){
  11.         if(S[i]>=m){
  12.             Sp[i] = m;
  13.         }else{
  14.             m = S[i];
  15.             Sp[i] = m;
  16.         }
  17.     }
  18.  
  19.     vector<int> ans;
  20.     for(int i=0;i<n-1;i++){
  21.         if(Sp[i] == S[i]){
  22.             ans.push_back(0);
  23.         }else{
  24.             int l = i+1;
  25.             int r = n-1;
  26.             while(l<r){
  27.                 int mid = (l+r)/2;
  28.                 if(Sp[mid]>S[i])r=mid-1;
  29.                 else if(Sp[mid]<S[i] && Sp[mid]!=0)l=mid+1;
  30.                 else {
  31.                     r = mid;
  32.                     break;}
  33.             }
  34.             if(Sp[r]>=S[i])ans.push_back(r-i-1);
  35.             else {ans.push_back(r-i);
  36.             }
  37.         }
  38.     }
  39.     ans.push_back(0);
  40.     return ans;
  41. }
  42.  
  43. int main() {
  44.     ios::sync_with_stdio(0);
  45.     cin.tie(0);
  46.     int T;
  47.     cin >> T;
  48.     for(int t_i=0; t_i<T; t_i++)
  49.     {   int n;
  50.         cin >> n;
  51.         vector<int> S(n);
  52.         for(int i_S=0; i_S<n; i_S++)
  53.         {
  54.         	cin >> S[i_S];
  55.         }
  56.         vector<int> out_;
  57.         out_ = solve(S,n);
  58.         cout << out_[0];
  59.         for(int i_out_=1; i_out_<out_.size(); i_out_++)
  60.         {
  61.         	cout << " " << out_[i_out_];
  62.         }
  63.         cout << "\n";
  64.     }
  65. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
1
5
5 4 3 2 1
stdout
copy 
4 3 2 1 0
https://ideone.com/DTjuyo
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!