Advertisement
Josif_tepe

Untitled

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