#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;
int type; // 1 for left edge, -1 for right edge
int bottomY;
int topY;
} Event;
int compare(const void *a, const void *b) {
Event *eventA = (Event *)a;
Event *eventB = (Event *)b;
if (eventA->x != eventB->x) {
return eventA->x - eventB->x;
}
return eventA->type - eventB->type; // Left edge before right edge
}
int calculate_y_length(Event *events, int active_count) {
int total_length = 0;
int current_start = -1;
int current_end = -1;
for (int i = 0; i < active_count; i++) {
if (events[i].bottomY > current_end) {
// Non-overlapping interval
if (current_start != -1) {
total_length += current_end - current_start;
}
current_start = events[i].bottomY;
current_end = events[i].topY;
} else {
// Overlapping interval
if (events[i].topY > current_end) {
current_end = events[i].topY;
}
}
}
// Add last active interval
if (current_start != -1) {
total_length += current_end - current_start;
}
return total_length;
}
int main() {
int N, K, L;
scanf("%d %d %d", &N, &K, &L);
Event
*events
= malloc
(2 * N
* sizeof(Event
)); for (int i = 1; i <= N; i++) {
int leftX = i * K - L;
int rightX = i * K + L;
int bottomY = i * K;
int topY = i * K + L;
// Left edge event
events[2 * (i - 1)] = (Event){leftX, 1, bottomY, topY};
// Right edge event
events[2 * (i - 1) + 1] = (Event){rightX, -1, bottomY, topY};
}
qsort
(events
, 2 * N
, sizeof(Event
), compare
);
int area = 0;
int last_x = events[0].x;
Event
*active_intervals
= malloc
(2 * N
* sizeof(Event
)); int active_count = 0;
for (int i = 0; i < 2 * N; i++) {
int x = events[i].x;
// Calculate area contribution from last_x to current x
if (active_count > 0) {
int y_length = calculate_y_length(active_intervals, active_count);
area += y_length * (x - last_x);
}
// Update active intervals
if (events[i].type == 1) { // Left edge
active_intervals[active_count++] = events[i];
} else { // Right edge
for (int j = 0; j < active_count; j++) {
if (active_intervals[j].bottomY == events[i].bottomY &&
active_intervals[j].topY == events[i].topY) {
// Remove the interval
active_intervals[j] = active_intervals[--active_count];
break;
}
}
}
last_x = x;
}
free(events);
free(active_intervals);
return 0;
}