1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct event {
int pos;
bool tip; // true za začetek, false za konec
};
int compar_events (const void * a, const void * b) {
if (((struct event *) a)->pos == ((struct event *) b)->pos)
return 0;
if (((struct event *) a)->pos < ((struct event *) b)->pos)
return -1;
return 1;
}
int main (void) {
struct event events[20000];
int M, N, x, d;
scanf("%d %d", &M, &N);
for (int i = 0; i < N; i++) {
scanf("%d %d", &x, &d);
events[2*i].pos = x-d >= 0 ? x-d : 0;
events[2*i].tip = true;
events[2*i+1].pos = x+d <= M ? x+d : M;
events[2*i+1].tip = false;
}
qsort(events, 2*N, sizeof events[0], compar_events);
int osv = 0;
int depth = 0;
int start;
for (int i = 0; i < 2*N; i++) {
// fprintf(stderr, "pos=%d\ttip=%d\n", events[i].pos, events[i].tip);
if (events[i].tip == true) {
if (depth == 0)
start = events[i].pos;
depth++;
}
if (events[i].tip == false) {
depth--;
if (depth == 0)
osv += events[i].pos - start;
}
}
if (depth != 0)
fprintf(stderr, "depth == %d\n", depth);
printf("%d\n", M-osv);
}
|
