2905번: 홍준이와 울타리

https://www.acmicpc.net/problem/2905

#include<stdio.h>
#include<deque>
using namespace std;
const int MAX_N = 1e6;
int b[MAX_N + 1], n, x, res;
deque<pair<int, int> > dq;
typedef long long ll;
ll tot;
int main() {
    scanf("%d %d", &n, &x);
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
        tot += b[i];
    }
    int s = 0, tmp;
    for (int i = 0; i<x; i++) {
        while (!dq.empty() && dq.back().second>b[i]) dq.pop_back();
        dq.push_back({ i, b[i] });
    }
    tmp = dq.front().second;
    for (int i = x; i <= n; i++) {
        while (!dq.empty() && dq.back().second>b[i]) dq.pop_back();
        dq.push_back({ i, b[i] });
        if (tmp != dq.front().second) {
            res += (i - s - 1) / x + 1;
            tot -= (ll)(i - s)*tmp;
            s = i;
            tmp = dq.front().second;
        }
        if (dq.front().first <= i - x) {
            int tp = dq.front().first;
            dq.pop_front();
            if (tmp != dq.front().second) {
                res += (tp - s) / x + 1;
                tot -= (ll)(tp - s + 1)*tmp;
                s = tp + 1;
                tmp = dq.front().second;
            }
        }
    }
    printf("%lld\n%d", tot, res);
    return 0;
}