Educational Codeforces Round 5 D. Longest k-Good Segment

問題

codeforces.com

解法

しゃくとり法やるだけ, なんですがバグらせまくりました…

区間系書くときは, 「閉区間か半開区間か」とか「区間がどのような性質を持っているか」とかは意識すべきですね。そういえば珠玉のプログラミングにもそんなことが書いてあったような気がする。いや 114514 年前に 1 回読んだだけだからはっきり覚えてないけど。
www.amazon.co.jp

今回の場合は, [l, r) という区間が, 常に K 個以下の種類の数を持つようにする, と決めてしゃくとりしています。

const int MAXN = 500050;
int a[MAXN], mp[2*MAXN];

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) scanf("%d", a+i);
    int r = 0, cnt = 0;
    pii ans = pii(-1, -1);
    for (int l = 0; l < N; l++) {
        while (r < N) {
            if (mp[a[r]]++ == 0) cnt++;
            if (cnt > K) {
                if (--mp[a[r]] == 0) cnt--;
                break;
            }
            r++;
        }
        if (ans.second-ans.first < r-l) {
            ans.first = l+1;
            ans.second = r;
        }
        if (--mp[a[l]] == 0) cnt--;
    }
    printf("%d %d\n", ans.first, ans.second);
    return 0;
}