5b.c (1607B)
1 /* For part 2 we save ranges as (first, last) instead of (first, length) */ 2 3 #include <inttypes.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 #define N 10000 9 #define ISNUM(c) (c >= '0' && c <= '9') 10 #define MIN(a, b) ((a)<(b)?(a):(b)) 11 #define MAX(a, b) ((a)>(b)?(a):(b)) 12 13 14 void append(int64_t dst[][2], int64_t src[][2], int64_t *nr, int64_t *nnr) { 15 for (int i = 0; i < *nnr; i++) { 16 dst[i+*nr][0] = src[i][0]; 17 dst[i+*nr][1] = src[i][1]; 18 } 19 *nr += *nnr; 20 *nnr = 0; 21 } 22 23 int64_t readl(int64_t nums[], char *buf) { 24 int64_t i; 25 for (i = 0; *buf; buf++) { 26 if (!ISNUM(*buf)) continue; 27 nums[i++] = atoll(buf); 28 while (ISNUM(*buf)) buf++; 29 } 30 return i; 31 } 32 33 int main() { 34 char *buf, line[N]; 35 int64_t i, li, ri, m, nr, nnr, r[3], range[N][2], next[N][2], aux[N]; 36 37 nnr = readl(aux, fgets(line, N, stdin)) / 2; 38 for (i = 0; i < nnr; i++) { 39 next[i][0] = aux[2*i]; 40 next[i][1] = aux[2*i+1] + next[i][0] - 1; 41 } 42 43 for (nr = 0; (buf = fgets(line, N, stdin)) != NULL; ) { 44 if (!ISNUM(*buf)) { 45 append(range, next, &nr, &nnr); 46 continue; 47 } 48 49 readl(r, buf); 50 for (i = 0; i < nr; i++) { 51 li = range[i][0]; 52 ri = range[i][1]; 53 if (li > ri || r[1] > ri || r[1]+r[2]-1 < li) continue; 54 range[i][1] = MIN(ri, r[1]-1); 55 next[nnr][0] = MAX(li, r[1]) + r[0]-r[1]; 56 next[nnr++][1] = MIN(ri, r[1]+r[2]-1) + r[0]-r[1]; 57 range[nr][0] = MAX(li, r[1]+r[2]); 58 range[nr++][1] = ri; 59 } 60 } 61 62 append(range, next, &nr, &nnr); 63 for (i = 0, m = -1; i < nr; i++) 64 if (range[i][0] <= range[i][1]) 65 m = m == -1 || m > range[i][0] ? range[i][0] : m; 66 67 printf("%" PRId64 "\n", m); 68 return 0; 69 }