fork download
copy 
  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
comments (?)
stdin
copy 
5
8
1
3
3
8
stdout
copy 
22
2
11
12
23
https://ideone.com/3XVJSX
language:
C++14 (gcc 8.3)
created:
6 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!