Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <cstring>
- #include <stack>
- #include <fstream>
- #include <set>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- int n, k;
- int arr[maxn];
- multiset<int> lower_values, greater_values;
- void insert_value(int x, ll& sum_lower, ll& sum_greater) {
- int max_lower_value = *lower_values.rbegin();
- if(max_lower_value < x) {
- greater_values.insert(x);
- sum_greater += x;
- if(greater_values.size() > k / 2) {
- int smallest_greater = *greater_values.begin();
- sum_greater -= smallest_greater;
- sum_lower -= smallest_greater;
- lower_values.insert(smallest_greater);
- greater_values.erase(greater_values.find(smallest_greater));
- }
- }
- else {
- lower_values.insert(x);
- sum_lower -= x;
- if(lower_values.size() > (k + 1) / 2) {
- int max_in_lower = *lower_values.rbegin();
- greater_values.insert(max_in_lower);
- lower_values.erase(lower_values.find(max_in_lower));
- sum_lower += max_in_lower;
- sum_greater += max_in_lower;
- }
- }
- }
- void remove_element(int x, ll& sum_lower, ll& sum_greater) {
- if(greater_values.find(x) != greater_values.end()) {
- greater_values.erase(greater_values.find(x));
- sum_greater -= x;
- }
- else if(lower_values.find(x) != lower_values.end()) {
- lower_values.erase(lower_values.find(x));
- sum_lower += x;
- }
- if(lower_values.empty()) {
- int smallest_in_greater = *greater_values.begin();
- lower_values.insert(smallest_in_greater);
- greater_values.erase(greater_values.find(smallest_in_greater));
- sum_greater -= smallest_in_greater;
- sum_lower -= smallest_in_greater;
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> k;
- for(int i = 0; i < n; i++) {
- cin >> arr[i];
- }
- ll sum_lower = -arr[0];
- ll sum_greater = 0;
- lower_values.insert(arr[0]);
- for(int i = 1; i < k; i++) {
- insert_value(arr[i], sum_lower, sum_greater);
- }
- ll median = *lower_values.rbegin();
- ll tmp = (ll) (lower_values.size()) * median + sum_lower;
- tmp += sum_greater - (ll) (greater_values.size()) * median;
- // cout << median << " ";
- cout << tmp << " ";
- for(int i = k; i < n; i++){
- if(k > 1) {
- remove_element(arr[i - k], sum_lower, sum_greater);
- insert_value(arr[i], sum_lower, sum_greater);
- }
- else {
- insert_value(arr[i], sum_lower, sum_greater);
- remove_element(arr[i - 1], sum_lower, sum_greater);
- }
- median = *lower_values.rbegin();
- tmp = (ll) (lower_values.size()) * median + sum_lower;
- tmp += sum_greater - (ll) (greater_values.size()) * median;
- cout << tmp << " " ;
- // cout << median << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement