Submission

------TTTT

Score: 0

User: Jokul

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

Language: c

Time: 1.096 second

Submitted On: 2025-03-08 11:10:45

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

typedef struct {
    long long position;
    int color;
} NewBead;

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

    long long *changePoints = (long long *)malloc(M * sizeof(long long));
    for (long long j = 0; j < M; ++j) {
        scanf("%lld", &changePoints[j]);
    }

    NewBead *newBeads = (NewBead *)malloc(K * sizeof(NewBead));
    for (long long i = 0; i < K; ++i) {
        scanf("%lld %d", &newBeads[i].position, &newBeads[i].color);
    }

    // Initialize the color of the beads
    int currentColor = 1; // Start with white (1)
    long long lastChange = 1;
    long long colorChanges = 0;

    // Count color changes in the original beads
    for (long long j = 0; j < M; ++j) {
        // Count the number of beads before the next change point
        for (long long pos = lastChange; pos < changePoints[j]; ++pos) {
            if (pos > 1 && currentColor != (pos % 2)) {
                colorChanges++;
            }
        }
        currentColor = 1 - currentColor; // Toggle color
        lastChange = changePoints[j];
    }
    // Handle the remaining beads after the last change point
    for (long long pos = lastChange; pos <= N; ++pos) {
        if (pos > 1 && currentColor != (pos % 2)) {
            colorChanges++;
        }
    }

    // Insert new beads and count color changes
    long long newBeadIndex = 0;
    for (long long i = 1; i <= N + K; ++i) {
        // Check if we need to insert a new bead
        if (newBeadIndex < K && newBeads[newBeadIndex].position == i) {
            // Insert the new bead
            if (newBeads[newBeadIndex].color != (i % 2)) {
                colorChanges++;
            }
            newBeadIndex++;
        } else {
            // Original bead color
            int originalColor = (i <= N) ? (i % 2) : (1 - (newBeadIndex % 2));
            if (originalColor != (i % 2)) {
                colorChanges++;
            }
        }
    }

    printf("%lld\n", colorChanges);

    // Free allocated memory
    free(changePoints);
    free(newBeads);

    return 0;
}