Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- typedef long long ll;
- multiset<int> smaller_values, greater_values;
- int n, k;
- void insert_value(int x, ll & difference_smaller, ll & sum_greater) {
- int max_in_smaller_values = *smaller_values.rbegin();
- if(max_in_smaller_values < x) {
- greater_values.insert(x);
- sum_greater += x;
- if(greater_values.size() > k / 2) {
- int min_in_greater = *greater_values.begin();
- smaller_values.insert(min_in_greater);
- greater_values.erase(greater_values.find(min_in_greater));
- difference_smaller -= min_in_greater;
- sum_greater -= min_in_greater;
- }
- }
- else {
- smaller_values.insert(x);
- difference_smaller -= x;
- if(smaller_values.size() > (k + 1) / 2) {
- int tmp_max_in_smaller = *smaller_values.rbegin();
- greater_values.insert(tmp_max_in_smaller);
- smaller_values.erase(smaller_values.find(tmp_max_in_smaller));
- sum_greater += tmp_max_in_smaller;
- difference_smaller += tmp_max_in_smaller;
- }
- }
- }
- void remove_element(int x, ll & difference_smaller, ll & sum_greater) {
- if(greater_values.find(x) != greater_values.end()) {
- greater_values.erase(greater_values.find(x));
- sum_greater -= x;
- }
- else if(smaller_values.find(x) != smaller_values.end()) {
- smaller_values.erase(smaller_values.find(x));
- difference_smaller += x;
- }
- if(smaller_values.empty()) {
- int min_in_greater = *greater_values.begin();
- smaller_values.insert(min_in_greater);
- greater_values.erase(greater_values.find(min_in_greater));
- difference_smaller -= min_in_greater;
- sum_greater -= min_in_greater;
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin >> n >> k;
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- ll difference_smaller = -v[0];
- ll sum_greater = 0;
- smaller_values.insert(v[0]);
- for(int i = 1; i < k; i++) {
- insert_value(v[i], difference_smaller, sum_greater);
- }
- ll result = sum_greater - (ll) (greater_values.size()) * (*smaller_values.rbegin());
- result += (ll) (smaller_values.size()) * (*smaller_values.rbegin()) + difference_smaller;
- cout << result << " ";
- for(int i = k; i < n; i++) {
- if(k > 1) {
- remove_element(v[i - k], difference_smaller, sum_greater);
- insert_value(v[i], difference_smaller, sum_greater);
- }
- else {
- insert_value(v[i], difference_smaller, sum_greater);
- remove_element(v[i - k], difference_smaller, sum_greater);
- }
- result = sum_greater - (ll) (greater_values.size()) * (*smaller_values.rbegin());
- result += (ll) (smaller_values.size()) * (*smaller_values.rbegin()) + difference_smaller;
- cout << result << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement