Advertisement
Josif_tepe

Untitled

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