Advertisement
Josif_tepe

Untitled

Feb 3rd, 2023
878
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. #include <stack>
  5. #include <fstream>
  6. #include <set>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 2e5 + 10;
  10. int n, k;
  11. int arr[maxn];
  12. multiset<int> lower_values, greater_values;
  13.  
  14. void insert_value(int x, ll& sum_lower, ll& sum_greater) {
  15.     int max_lower_value = *lower_values.rbegin();
  16.    
  17.     if(max_lower_value < x) {
  18.         greater_values.insert(x);
  19.        
  20.         sum_greater += x;
  21.         if(greater_values.size() > k / 2) {
  22.             int smallest_greater = *greater_values.begin();
  23.             sum_greater -= smallest_greater;
  24.             sum_lower -= smallest_greater;
  25.             lower_values.insert(smallest_greater);
  26.             greater_values.erase(greater_values.find(smallest_greater));
  27.         }
  28.     }
  29.     else {
  30.         lower_values.insert(x);
  31.         sum_lower -= x;
  32.         if(lower_values.size() > (k + 1) / 2) {
  33.             int max_in_lower = *lower_values.rbegin();
  34.             greater_values.insert(max_in_lower);
  35.             lower_values.erase(lower_values.find(max_in_lower));
  36.             sum_lower += max_in_lower;
  37.             sum_greater += max_in_lower;
  38.         }
  39.     }
  40. }
  41. void remove_element(int x,  ll& sum_lower, ll& sum_greater) {
  42.     if(greater_values.find(x) != greater_values.end()) {
  43.         greater_values.erase(greater_values.find(x));
  44.         sum_greater -= x;
  45.     }
  46.     else if(lower_values.find(x) != lower_values.end()) {
  47.         lower_values.erase(lower_values.find(x));
  48.         sum_lower += x;
  49.     }
  50.    
  51.     if(lower_values.empty()) {
  52.         int smallest_in_greater = *greater_values.begin();
  53.         lower_values.insert(smallest_in_greater);
  54.         greater_values.erase(greater_values.find(smallest_in_greater));
  55.         sum_greater -= smallest_in_greater;
  56.         sum_lower -= smallest_in_greater;
  57.     }
  58. }
  59. int main() {
  60.     ios_base::sync_with_stdio(false);
  61.     cin >> n >> k;
  62.    
  63.     for(int i = 0; i < n; i++) {
  64.         cin >> arr[i];
  65.     }
  66.     ll sum_lower = -arr[0];
  67.     ll sum_greater = 0;
  68.     lower_values.insert(arr[0]);
  69.     for(int i = 1; i < k; i++) {
  70.         insert_value(arr[i], sum_lower, sum_greater);
  71.     }
  72.  
  73.     ll median = *lower_values.rbegin();
  74.    
  75.     ll tmp = (ll) (lower_values.size()) * median + sum_lower;
  76.     tmp += sum_greater - (ll) (greater_values.size()) * median;
  77. //    cout << median << " ";
  78.     cout << tmp << " ";
  79.     for(int i = k; i < n; i++){
  80.         if(k > 1) {
  81.             remove_element(arr[i - k], sum_lower, sum_greater);
  82.             insert_value(arr[i], sum_lower, sum_greater);
  83.         }
  84.         else {
  85.             insert_value(arr[i], sum_lower, sum_greater);
  86.             remove_element(arr[i - 1], sum_lower, sum_greater);
  87.         }
  88.         median = *lower_values.rbegin();
  89.         tmp = (ll) (lower_values.size()) * median + sum_lower;
  90.         tmp += sum_greater - (ll) (greater_values.size()) * median;
  91.         cout << tmp << " " ;
  92. //        cout << median << " ";
  93.     }
  94.     return 0;
  95. }
  96.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement