fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define all(x) x.begin(), x.end()
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. typedef long long ll;
  12.  
  13. #define inf 1e9
  14. #define MOD 1000000007
  15. #define vint vector<int>
  16. #define vll vector<ll>
  17. #define no cout << "NO" << endl;
  18.  
  19. void solve() {
  20.     ll n ; cin >> n ;
  21.     vector < ll > a(n);
  22.     map < ll , ll>freq  , mp ;
  23.     map < ll , bool  > visfreq , vismp ;
  24.     for (int  i = 0 ; i <  n ; i ++ ) {
  25.         cin >> a[i] ;
  26.         freq[a[i]] ++ ;
  27.         visfreq[a[i]] = 1 ;
  28.     }
  29.     bool test = false ;
  30.     for (auto e :  freq ) {
  31.         if (e.second  > 1 ) {
  32.             mp[e.first] = e.second  -1 ;
  33.             freq[e.first] = 1 ;
  34.             vismp[e.first] = 1 ;
  35.         }
  36.     }
  37.     ll ans = 0 ;
  38.     for (int i = 0 ; i<=  n;  i ++ ){
  39.         if (i == 0 ) {
  40.             ll x = 0 ;
  41.             if (visfreq[i])x ++ ;
  42.             if (vismp[i])x+= mp[i] ;
  43.             cout << ans + x <<" ";
  44.             continue ;
  45.         }
  46.        if (test ) {
  47.            cout <<-1  << " " ; continue ;
  48.        }
  49.         if (visfreq[i-1] ) {
  50.             ll x = 0 ;
  51.             if (visfreq[i])x ++ ;
  52.             if (vismp[i])x+= mp[i] ;
  53.             cout << ans + x <<" ";
  54.             continue ;
  55.         }
  56.         auto it1  = mp.upper_bound(i-1) ;
  57.  
  58.         if (it1 == mp . begin() || mp.empty()) {
  59.             test = true ;
  60.             cout << -1 <<" " ; continue ;
  61.         }
  62.  
  63.         auto it = prev(it1) ;
  64.         ll element = (*it).first ;
  65.         ans+=(i - element -1  );
  66.         mp[element]-- ;
  67.         visfreq[i-1] = 1 ;
  68.         if (!mp[element]) {
  69.         //      cout << element <<"hhh";
  70.             mp.erase(element) ; vismp[element] = 0 ;
  71.         }
  72.         ll x = 0 ;
  73.         if (visfreq[i])x ++ ;
  74.         if (vismp[i])x+= vismp[i] ;
  75.         cout << ans + x <<" ";
  76.     }
  77.     cout << endl ;
  78.  
  79.  
  80.  
  81. }
  82.  
  83.  
  84.  
  85. int main() {
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.  
  89. #ifndef ONLINE_JUDGE
  90.     freopen("input.txt", "r", stdin);
  91.     freopen("output.txt", "w", stdout);
  92. #endif
  93.  
  94.  
  95.     int t = 1 ;
  96.     cin >> t;
  97.     while (t--) {
  98.         solve();
  99.     }
  100.  
  101.     return 0;
  102. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/plsdtD
language:
C++ (gcc 8.3)
created:
4 days 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!