3020번: 개똥벌레

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


$O(n+h)$

prefix sum을 이용한다.

#include<cstdio>
int n, h, c[500000], s, p = 1e9, q;
int main() {
    scanf("%d%d", &n, &h);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        i & 1 ? c[h - x]++ : (c[0]++, c[x]--);
    }
    for (int i = 0; i < h; i++) {
        s += c[i];
        if (s < p) p = s, q = 0;
        q += p == s;
    }
    printf("%d %d", p, q);
    return 0;
}