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;
- multiset<int> smaller_values, greater_values;
- int n, k;
- void insert_value(int x) {
- int max_in_smaller_values = *smaller_values.rbegin();
- if(max_in_smaller_values < x) {
- greater_values.insert(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));
- }
- }
- else {
- smaller_values.insert(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));
- }
- }
- }
- void remove_element(int x) {
- if(greater_values.find(x) != greater_values.end()) {
- greater_values.erase(greater_values.find(x));
- }
- else if(smaller_values.find(x) != smaller_values.end()) {
- smaller_values.erase(smaller_values.find(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));
- }
- }
- 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];
- }
- smaller_values.insert(v[0]);
- for(int i = 1; i < k; i++) {
- insert_value(v[i]);
- }
- cout << *smaller_values.rbegin() << " ";
- for(int i = k; i < n; i++) {
- if(k > 1) {
- remove_element(v[i - k]);
- insert_value(v[i]);
- }
- else {
- insert_value(v[i]);
- remove_element(v[i - k]);
- }
- cout << *smaller_values.rbegin() << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement