fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6. #define all(x) x.begin(), x.end()
  7. #define rep(i,a,b) for(int i = a; i <= b; i++)
  8. #define per(i,b,a) for(int i = b; i >= a; i--)
  9. #define lower lower_bound
  10. #define upper upper_bound
  11. #define sz(x) (int)x.size()
  12.  
  13. const int N = 1e6 + 1 ;
  14.  
  15. ll t[2][N] ;
  16. int n , k , a[N] ;
  17.  
  18. void upd(int id , int x , int p){
  19. 	while(id <= n){
  20. 		t[p][id] += x ;
  21. 		id += (id & (-id)) ;
  22. 	}
  23. }
  24.  
  25. ll get(int id , int p){
  26. 	ll sum = 0 ;
  27. 	while(id > 0) sum += t[p][id] , id -= (id & (-id)) ;
  28. 	return sum ;	
  29. }
  30.  
  31. void solve(){
  32. 	cin >> n >> k ;
  33. 	int mn , mx ;
  34. 	mn = INT_MAX ;
  35. 	mx = INT_MIN ;
  36. 	set<int> kf ;
  37. 	rep(i , 1 , n){
  38. 		cin >> a[i] ;
  39. 		kf.insert(a[i]) ;
  40. 		// kf.insert(a[i] - 1) ;
  41. 		mn = min(mn , a[i]) ;
  42. 		mx = max(mx , a[i]) ;
  43. 		if(k == 1) cout << 0 << ' '; 
  44. 	}
  45. 	map<int,int> compress ;
  46. 	int cnt = 0 ;
  47. 	for(auto x : kf) compress[x] = ++cnt ;                  
  48. 	if(k == 1) return ;
  49. 	int l , r ;   
  50. 	multiset<int> x , y ;
  51. 	l = 1 , r = 0 ;
  52. 	ll ans = 0 ;
  53. 	while(l <= n - k + 1){
  54. 		while(r <= n && sz(x) + sz(y) < k){
  55. 			r++ ;
  56. 			int cnt = k / 2 ;
  57. 			if(sz(x) < cnt){
  58. 				x.insert(a[r]);
  59. 				upd(compress[a[r]] , a[r] , 0) ;
  60. 			}else{
  61. 				if(a[r] <= *(--x.end())){
  62. 					x.insert(a[r]) ;
  63. 					upd(compress[a[r]] , a[r] , 0) ;
  64. 					auto it = x.end() ; it-- ;
  65. 					upd(compress[*it] , *it , 1) ;
  66. 					y.insert(*it) ;
  67. 					upd(compress[*it] , -*it , 0) ;
  68. 					x.erase(it) ;
  69. 				}else{
  70. 					upd(compress[a[r]] , a[r] , 1) ;
  71. 					y.insert(a[r]) ;
  72. 				}
  73. 			}
  74. 		}
  75. 		ll mid ;
  76. 		if(k & 1){
  77. 			mid = *y.begin()  ;
  78. 		}else{
  79. 			mid = *(--x.end()) ;
  80. 		}                               
  81. 		ll L , R ;
  82. 		ll del1 , del2 ;
  83. 		if(k & 1){
  84. 			L = mid * sz(x) + mid ;
  85. 			del1 = get(compress[mid] , 0) + mid ; 
  86. 			R = mid * sz(y) ;
  87. 			del2 = get(compress[mx] , 1) - get(compress[mid] - 1 , 1) ;
  88. 		}else{
  89. 			L = mid * sz(x) ;
  90. 			del1 = get(compress[mid] , 0) ;
  91. 			R = mid * sz(y) + mid ;
  92. 			del2 = get(compress[mx] , 1) - get(compress[mid] - 1 , 1) + mid ;
  93. 		}
  94. 		ans = 0 ;
  95. 		// cout << del1 << ' ' << del2 << " " << ' ' << L << ' ' << R << " "  ;
  96. 		ans += (L - del1) ;
  97. 		ans += (del2 - R) ; 
  98. 		cout << ans << " " ;
  99. 		if(x.find(a[l]) != x.end()){
  100. 			x.erase(x.find(a[l])) ;
  101. 			upd(compress[a[l]] , -a[l] , 0) ;
  102. 			if(sz(y)) x.insert(*(y.begin())) , upd(compress[*y.begin()] , *y.begin() , 0) , upd(compress[*y.begin()] , -*y.begin() , 1) , y.erase(y.begin()) ;
  103. 		}else{
  104. 			y.erase(y.find(a[l])) ;
  105. 			upd(compress[a[l]] , -a[l] , 1) ;
  106. 		}
  107. 		l++ ;
  108. 	}
  109. }                                                  
  110.  
  111. int main(){
  112.     #ifdef Wizzard
  113.         freopen(".in" , "r" , stdin) ;     
  114.     #endif
  115.     ios::sync_with_stdio(false) ;
  116.     cin.tie(0) ;
  117.     int t = 1 ;
  118.     // cin >> t ;
  119.     rep(i , 1 , t){
  120.         solve() ;
  121.     }
  122. }
Runtime error #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BUXxJO
language:
C++ (gcc 8.3)
created:
1 year 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!