fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define pb push_back
  6. #define ll long long int
  7.  
  8. typedef pair<int,int> pii;
  9.  
  10. ll tme , ans[50005];
  11. int n , ner , idx , ls , val , k , it , bit[50005];
  12.  
  13. void update( int idx , int val , int n )
  14. {
  15. while( idx <= n )
  16. {
  17. bit[idx] += val;
  18. idx += idx&(-idx);
  19. }
  20. }
  21.  
  22. int query( int idx )
  23. {
  24. int sum = 0 ;
  25. while( idx > 0 )
  26. {
  27. sum += bit[idx];
  28. idx -= idx&(-idx);
  29. }
  30. return sum;
  31. }
  32.  
  33.  
  34. bool cmp( pii a , pii b )
  35. {
  36. if( a.fi == b.fi )
  37. {
  38. return a.se < b.se;
  39. }
  40. return a.fi < b.fi;
  41. }
  42.  
  43. int main() {
  44.  
  45. cin >> n;
  46. vector<pii> arr;
  47. for( int i = 1 ; i <= n ;i++)
  48. {
  49. int a ;
  50. cin >> a;
  51. arr.pb({a,i});
  52. /*update the ith index that it is initially present and the ith
  53.   task has not been completed
  54.   1-not completed
  55.   0-completed*/
  56. update(i,1,n);
  57. }
  58. //sorting in increasing order
  59. sort( arr.begin() , arr.end() , cmp);
  60.  
  61. for( int i = 0 ; i < n ; i++)
  62. {
  63. val = arr[i].fi;
  64. idx = arr[i].se;
  65. //ner :- number of elements(tasks) remaining
  66. ner = n-i;
  67. /* find out number of task before current task which are not completed in
  68. the origninal array*/
  69. ls = query( idx );
  70.  
  71. /* iteration required to make the current task zero = value of the task
  72. so if the iteration is not the 1 less than val then we need to make it
  73. come to iteration 1 less than the iteration required
  74. eg:- val - 5 , it = 2 , then we make it = 4 by adding ner*(5-2-1) = ner*4
  75. */
  76. if( val-1 > it )
  77. {
  78. tme += (val - 1 - it)*1ll*ner ;
  79. }
  80. /* in tme add the position of the current element
  81. after considerating how many task has been done.*/
  82. ans[idx] = ls + tme;
  83.  
  84. /*k is for counting how many elements have same
  85. value as the current element*/
  86. k = 0;
  87. for( int j = i+1 ; j < n ; j++)
  88. {
  89. if( val == arr[j].fi )
  90. {
  91. /* if element has same value then it's iteration will be equal
  92. to the iteration of current element
  93. then just add the position of the task in tme to get it's answer
  94. */
  95. ls = query( arr[j].se );
  96. k++;
  97. ans[arr[j].se] = tme + ls;
  98.  
  99. }
  100. else
  101. {
  102. break;
  103. }
  104. }
  105.  
  106. for( int j = i ; j < n ; j++)
  107. {
  108. if( val != arr[j].fi )
  109. {
  110. break;
  111. }
  112. /*updating values to -1 because the task have been ompleted
  113. and won't be considered in next iteration*/
  114. update(idx,-1,n);
  115. }
  116. /*make itreation equal to current value , similar update tme
  117. for representing time past till current iteration
  118. and update i */
  119. tme += ner;
  120. it = val;
  121. i = i+k;
  122.  
  123. }
  124. for( int i = 1 ; i <= n ;i++)
  125. {
  126. cout << ans[i] << "\n";
  127. }
  128.  
  129.  
  130. return 0;
  131. }
Success #stdin #stdout 0s 15824KB
stdin
5
8
1
3
3
8
stdout
22
2
11
12
23