Submission

Score: 85

User: Jokul

Problemset: ละลานตา

Language: c

Time: 0.007 second

Submitted On: 2025-04-09 13:01:30

#include <stdio.h>
#include <stdlib.h>

#define MAX_COLOR 100000

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    int *colors = (int *)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        scanf("%d", &colors[i]);
    }

    int left = 0, right = 0;
    int count = 0;
    int color_count[MAX_COLOR + 1] = {0}; // To count occurrences of each color
    int unique_colors = 0;

    while (right < N) {
        // Expand the right end of the window
        if (color_count[colors[right]] == 0) {
            unique_colors++;
        }
        color_count[colors[right]]++;
        right++;

        // While we have at least K unique colors, count the segments
        while (unique_colors >= K) {
            count += (N - right + 1); // All segments from left to right are valid

            // Contract the left end of the window
            color_count[colors[left]]--;
            if (color_count[colors[left]] == 0) {
                unique_colors--;
            }
            left++;
        }
    }

    printf("%d\n", count);
    free(colors);
    return 0;
}