Submission #37172703

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double PI = acos(-1);



int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    priority_queue<P> q1;
    priority_queue<P, vector<P>, greater<P>> q2;
    map<P, bool> inq1, valid; 
    ll nowsum = 0;
    rep(i,m) {
        valid[P(a[i], -i)] = true;
        if (i < k) {
            q1.push(P(a[i], -i));
            inq1[P(a[i], -i)] = true;
            nowsum += a[i];
        } else {
            P nowmax = q1.top();
            if (P(a[i], -i) < nowmax) {

                q1.pop();
                inq1[nowmax] = false;
                nowsum -= nowmax.first;
                q2.push(nowmax);

                q1.push(P(a[i], -i));
                inq1[P(a[i], -i)] = true;
                nowsum += a[i];

            } else {
                q2.push(P(a[i], -i));
            }
        }
    }
    cout << nowsum << " ";

    rep(i,n-m) {
        // a[i] を抜く
        P pi = P(a[i], -i);
        // cout << q1.size() << " " << q2.size() << endl;
        if (inq1[pi]) {
            nowsum -= pi.first;
            inq1[pi] = false;

            while (1) {
                if (q2.empty()) break;
                P p = q2.top();
                q2.pop();
                if (!valid[p]) continue;
                q1.push(p);
                inq1[p] = true;
                nowsum += p.first;
                break;
            }
        } 
        valid[pi] = false;

        // cout << 1 << endl;

        // a[i+m] を入れる
        P pim = P(a[i+m], -(i+m));
        bool okin = false;
        while (1) {
            if (q1.empty()) {
                q1.push(pim);
                inq1[pim] = true;
                nowsum += pim.first;
                break;
            }
            P p = q1.top();
            q1.pop();
            if (!valid[p]) continue;
            if (pim < p) {

                inq1[p] = false;
                nowsum -= p.first;
                q2.push(p);

                q1.push(pim);
                inq1[pim] = true;
                nowsum += pim.first;

            } else {
                q2.push(pim);
                q1.push(p);
            }
            break;
        }
        valid[pim] = true;

        cout << nowsum << " ";
    }
    cout << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78:14: warning: unused variable ‘okin’ [-Wunused-variable]
   78 |         bool okin = false;
      |              ^~~~

Judge Result