sliding_window_cost.cpp (1810B)
1 #include <bits/stdc++.h> 2 #include <ext/pb_ds/tree_policy.hpp> 3 #include <ext/pb_ds/assoc_container.hpp> 4 5 using namespace std; 6 using namespace __gnu_pbds; 7 8 template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 9 template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 10 11 using ui = unsigned int; 12 using ul = unsigned long; 13 using ll = long long; 14 using ull = unsigned long long; 15 16 using vi = vector<int>; 17 using vui = vector<ui>; 18 using vl = vector<long>; 19 using vul = vector<ul>; 20 using vll = vector<ll>; 21 using vull = vector<ull>; 22 23 void solve() 24 { 25 int n, k; 26 cin >> n >> k; 27 multiset<int> l; 28 multiset<int> r; 29 queue<int> q; 30 ll sl = 0; 31 ll sr = 0; 32 int x; 33 cin >> x; 34 l.insert(x); 35 sl += x; 36 q.push(x); 37 if (k == 1) { 38 for (int i = 0; i < n; i++) 39 cout << "0 "; 40 cout << "\n"; 41 return; 42 } 43 for (int i = 1; i < n; i++) { 44 cin >> x; 45 q.push(x); 46 int a = *l.rbegin(); 47 if (a < x) { 48 r.insert(x); 49 sr += x; 50 if (r.size() > k / 2) { 51 sl += *r.begin(); 52 sr -= *r.begin(); 53 l.insert(*r.begin()); 54 r.erase(r.find(*r.begin())); 55 } 56 } else { 57 l.insert(x); 58 sl += x; 59 if (l.size() > (k+1) / 2) { 60 sl -= *l.rbegin(); 61 sr += *l.rbegin(); 62 r.insert(*l.rbegin()); 63 l.erase(l.find(*l.rbegin())); 64 } 65 } 66 67 if (i >= k - 1) { 68 int v = q.front(); 69 cout << sr - sl + (k % 2 ? *l.rbegin() : 0) << " "; 70 if (r.find(v) != r.end()) { 71 r.erase(r.find(v)); 72 sr -= v; 73 } 74 else { 75 l.erase(l.find(v)); 76 sl -= v; 77 } 78 79 if (l.empty()) { 80 sl += *r.begin(); 81 sr -= *r.begin(); 82 l.insert(*r.begin()); 83 r.erase(r.find(*r.begin())); 84 } 85 q.pop(); 86 } 87 } 88 cout << "\n"; 89 } 90 91 int main() 92 { 93 ios::sync_with_stdio(0); 94 cin.tie(0); 95 solve(); 96 }