Submission

-------TTT

Score: 0

User: Jokul

Problemset: สร้อยสลับสี (ยาวมาก)

Language: c

Time: 1.091 second

Submitted On: 2025-03-08 18:57:35

#include <stdio.h>

typedef struct {
    long long start;
    long long end;
    int color; // 0 for black, 1 for white
} Interval;

int main() {
    long long N, M, K;
    scanf("%lld %lld %lld", &N, &M, &K);

    Interval intervals[100001]; // Maximum M is 100,000
    int intervalCount = 0;

    // Read the intervals for color changes
    if (M > 0) {
        long long x;
        scanf("%lld", &x);
        intervals[intervalCount++] = (Interval){1, x - 1, 1}; // White until X1 - 1

        for (int j = 1; j <= M; j++) {
            scanf("%lld", &x);
            if (j % 2 == 1) { // Odd index, change to black
                intervals[intervalCount - 1].end = x - 1; // Close previous interval
                intervals[intervalCount++] = (Interval){x, 0, 0}; // Start black
            } else { // Even index, change to white
                intervals[intervalCount - 1].end = x - 1; // Close previous interval
                intervals[intervalCount++] = (Interval){x, 0, 1}; // Start white
            }
        }
        // Close the last interval
        intervals[intervalCount - 1].end = N;
    } else {
        // If M == 0, all are white
        intervals[intervalCount++] = (Interval){1, N, 1};
    }

    // Read the new beads
    long long A[100001];
    int C[100001];
    for (int i = 0; i < K; i++) {
        scanf("%lld %d", &A[i], &C[i]);
    }

    // Insert new beads and count color changes
    int changeCount = 0;
    int currentColor = intervals[0].color;
    long long currentPos = 1;

    for (int i = 0; i < intervalCount; i++) {
        long long start = intervals[i].start;
        long long end = intervals[i].end;
        int color = intervals[i].color;

        // Process the interval before the new beads
        while (currentPos < start) {
            if (currentColor != color) {
                changeCount++;
                currentColor = color;
            }
            currentPos++;
        }

        // Process the new beads
        while (currentPos <= end && (i < K && currentPos == A[i])) {
            if (currentColor != C[i]) {
                changeCount++;
                currentColor = C[i];
            }
            currentPos++;
            i++;
        }

        // Process the remaining interval
        while (currentPos <= end) {
            if (currentColor != color) {
                changeCount++;
                currentColor = color;
            }
            currentPos++;
        }
    }

    printf("%d\n", changeCount);
    return 0;
}