Submission #37169519

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#include <queue>
#ifdef MY_LOCAL
#    include "helper.h"
#else
#    define debug(...)
#endif
using ll = long long;
using pii = std::pair<int, int>;
constexpr int inf = 0x3f3f3f3f;
constexpr ll inf2 = 1LL * inf * inf;
constexpr int mod = 998244353;
constexpr int mod2 = 1e9 + 7;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    multiset<int> all(a.begin(), a.begin() + m);
    multiset<int> S;
    for (int i = 0; i < m; ++i) {
        S.insert(a[i]);
        all.erase(all.find(a[i]));
        if (S.size() > k) {
            all.insert(*S.rbegin());
            S.erase(S.find(*S.rbegin()));
        }
    }
    assert(all.size() + S.size() == m);
    ll tot = 0;
    for (int x : S) tot += x;
    cout << tot << ' ';

    for (int i = m; i < n; ++i) {
        int x = a[i - m];

        all.insert(a[i]);
        auto it = S.find(x);
        if (it == S.end()) {
            all.erase(all.find(x));
            if (a[i] < *S.rbegin()) {
                all.erase(all.find(a[i]));
                all.insert(*S.rbegin());
                tot -= *S.rbegin();
                S.erase(S.find(*S.rbegin()));
                S.insert(a[i]);
                tot += a[i];
            }

        } else {
            S.erase(S.find(x));
            tot -= x;

            tot += *all.begin();
            S.insert(*all.begin());
            all.erase(all.begin());
        }
        cout << tot << ' ';
        assert(all.size() + S.size() == m);
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:22: warning: comparison of integer expressions of different signedness: ‘std::multiset<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   45 |         if (S.size() > k) {
      |             ~~~~~~~~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from ./Main.cpp:5:
./Main.cpp:50:34: warning: comparison of integer expressions of different signedness: ‘std::multiset<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   50 |     assert(all.size() + S.size() == m);
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~
./Main.cpp:80:38: warning: comparison of integer expressions of different signedness: ‘std::multiset<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   80 |         assert(all.size() + S.size() == m);
      |                ~~~~~~~~~~~~~~~~~~~~~~^~~~

Judge Result