# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

924278 | 2024-02-08T18:56:39 Z | rainboy | None (KOI16_dd) | C | 92 ms | 9920 KB |

#include <stdio.h> #include <string.h> #define N 100001 #define N_ (1 << 18) /* N_ = pow2(ceil(log2(N * 2))) */ int min(int a, int b) { return a < b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int xx[N], yy[N * 2], yy_[N * 2], hh[N * 2]; int *ww; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (ww[ii[j]] == ww[i_]) j++; else if (ww[ii[j]] < ww[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } int st[N_ * 2], n_; int min_(int i, int j) { return j == -1 || i != -1 && xx[i] < xx[j] ? i : j; } void update(int l, int r, int x) { for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) { if ((l & 1) == 1) st[l] = min_(st[l], x), l++; if ((r & 1) == 0) st[r] = min_(st[r], x), r--; } } int query(int i) { int x = -1; for (i += n_; i > 0; i >>= 1) x = min_(x, st[i]); return x; } int main() { static int ii[N * 2], jj[N * 2], dp[N * 2]; static char used[N * 2], used_[N * 2]; int n, m, x, y, y_, h, i, i0, i1, j, j0, j1, k; scanf("%d%d%d", &n, &y_, &x), n++; xx[0] = 0, yy[0 << 1 | 0] = y_, yy[0 << 1 | 1] = y_; for (i = 1; i < n; i++) scanf("%d%d%d", &xx[i], &yy[i << 1 | 0], &yy[i << 1 | 1]); for (i = 0; i < n * 2; i++) ii[i] = i; ww = yy, sort(ii, 0, n * 2); m = 0; for (i = 0; i < n * 2; i = j) { j = i, y = yy[ii[i]]; while (j < n * 2 && yy[ii[j]] == y) hh[ii[j++]] = m; yy_[m++] = y; } n_ = 1; while (n_ < n * 2) n_ <<= 1; memset(st, -1, n_ * 2 * sizeof *st); for (i = 0; i < n; i++) ii[i] = i; ww = xx, sort(ii, 0, n); for (h = n - 1; h >= 0; h--) { i = ii[h], i0 = i << 1 | 0, i1 = i << 1 | 1; j = jj[i0] = query(hh[i0]); if (j == -1) dp[i0] = 0; else { j0 = j << 1 | 0, j1 = j << 1 | 1; dp[i0] = min(dp[j0] + yy[i0] - yy[j0], dp[j1] + yy[j1] - yy[i0]); } j = jj[i1] = query(hh[i1]); if (j == -1) dp[i1] = 0; else { j0 = j << 1 | 0, j1 = j << 1 | 1; dp[i1] = min(dp[j0] + yy[i1] - yy[j0], dp[j1] + yy[j1] - yy[i1]); } update(hh[i0] + 1, hh[i1] - 1, i); } printf("%d\n", x + dp[0]); used[0 << 1 | 0] = used[0 << 1 | 1] = 1; for (h = 0; h < n; h++) { i = ii[h], i0 = i << 1 | 0, i1 = i << 1 | 1; i = ii[h]; if (used[i0]) { j = jj[i0]; if (j == -1) used_[hh[i0]] = 1; else { j0 = j << 1 | 0, j1 = j << 1 | 1; if (dp[i0] == dp[j0] + yy[i0] - yy[j0]) used[j0] = 1; if (dp[i0] == dp[j1] + yy[j1] - yy[i0]) used[j1] = 1; } } if (used[i1]) { j = jj[i1]; if (j == -1) used_[hh[i1]] = 1; else { j0 = j << 1 | 0, j1 = j << 1 | 1; if (dp[i1] == dp[j0] + yy[i1] - yy[j0]) used[j0] = 1; if (dp[i1] == dp[j1] + yy[j1] - yy[i1]) used[j1] = 1; } } } k = 0; for (h = 0; h < m; h++) if (used_[h]) k++; printf("%d", k); for (h = 0; h < m; h++) if (used_[h]) printf(" %d", yy_[h]); printf("\n"); return 0; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 4 ms | 6492 KB | Output is correct |

2 | Correct | 1 ms | 6492 KB | Output is correct |

3 | Correct | 1 ms | 6492 KB | Output is correct |

4 | Correct | 1 ms | 6492 KB | Output is correct |

5 | Correct | 1 ms | 6492 KB | Output is correct |

6 | Correct | 1 ms | 6492 KB | Output is correct |

7 | Correct | 1 ms | 6492 KB | Output is correct |

8 | Correct | 1 ms | 6492 KB | Output is correct |

9 | Correct | 1 ms | 6568 KB | Output is correct |

10 | Correct | 1 ms | 6492 KB | Output is correct |

11 | Correct | 1 ms | 6492 KB | Output is correct |

12 | Correct | 1 ms | 6492 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 4 ms | 6492 KB | Output is correct |

2 | Correct | 1 ms | 6492 KB | Output is correct |

3 | Correct | 1 ms | 6492 KB | Output is correct |

4 | Correct | 1 ms | 6492 KB | Output is correct |

5 | Correct | 1 ms | 6492 KB | Output is correct |

6 | Correct | 1 ms | 6492 KB | Output is correct |

7 | Correct | 1 ms | 6492 KB | Output is correct |

8 | Correct | 1 ms | 6492 KB | Output is correct |

9 | Correct | 1 ms | 6568 KB | Output is correct |

10 | Correct | 1 ms | 6492 KB | Output is correct |

11 | Correct | 1 ms | 6492 KB | Output is correct |

12 | Correct | 1 ms | 6492 KB | Output is correct |

13 | Correct | 1 ms | 6488 KB | Output is correct |

14 | Correct | 1 ms | 6492 KB | Output is correct |

15 | Correct | 1 ms | 6596 KB | Output is correct |

16 | Correct | 1 ms | 6492 KB | Output is correct |

17 | Correct | 1 ms | 6488 KB | Output is correct |

18 | Correct | 1 ms | 6492 KB | Output is correct |

19 | Correct | 1 ms | 6492 KB | Output is correct |

20 | Correct | 2 ms | 6492 KB | Output is correct |

21 | Correct | 1 ms | 6492 KB | Output is correct |

22 | Correct | 1 ms | 6492 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 4 ms | 6492 KB | Output is correct |

2 | Correct | 1 ms | 6492 KB | Output is correct |

3 | Correct | 1 ms | 6492 KB | Output is correct |

4 | Correct | 1 ms | 6492 KB | Output is correct |

5 | Correct | 1 ms | 6492 KB | Output is correct |

6 | Correct | 1 ms | 6492 KB | Output is correct |

7 | Correct | 1 ms | 6492 KB | Output is correct |

8 | Correct | 1 ms | 6492 KB | Output is correct |

9 | Correct | 1 ms | 6568 KB | Output is correct |

10 | Correct | 1 ms | 6492 KB | Output is correct |

11 | Correct | 1 ms | 6492 KB | Output is correct |

12 | Correct | 1 ms | 6492 KB | Output is correct |

13 | Correct | 1 ms | 6488 KB | Output is correct |

14 | Correct | 1 ms | 6492 KB | Output is correct |

15 | Correct | 1 ms | 6596 KB | Output is correct |

16 | Correct | 1 ms | 6492 KB | Output is correct |

17 | Correct | 1 ms | 6488 KB | Output is correct |

18 | Correct | 1 ms | 6492 KB | Output is correct |

19 | Correct | 1 ms | 6492 KB | Output is correct |

20 | Correct | 2 ms | 6492 KB | Output is correct |

21 | Correct | 1 ms | 6492 KB | Output is correct |

22 | Correct | 1 ms | 6492 KB | Output is correct |

23 | Correct | 1 ms | 6492 KB | Output is correct |

24 | Correct | 1 ms | 6492 KB | Output is correct |

25 | Correct | 1 ms | 6488 KB | Output is correct |

26 | Correct | 1 ms | 6492 KB | Output is correct |

27 | Correct | 1 ms | 6492 KB | Output is correct |

28 | Correct | 2 ms | 6492 KB | Output is correct |

29 | Correct | 1 ms | 6492 KB | Output is correct |

30 | Correct | 2 ms | 6492 KB | Output is correct |

31 | Correct | 2 ms | 6492 KB | Output is correct |

32 | Correct | 1 ms | 6488 KB | Output is correct |

33 | Correct | 1 ms | 6488 KB | Output is correct |

34 | Correct | 1 ms | 6492 KB | Output is correct |

35 | Correct | 2 ms | 6492 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 4 ms | 6492 KB | Output is correct |

2 | Correct | 1 ms | 6492 KB | Output is correct |

3 | Correct | 1 ms | 6492 KB | Output is correct |

4 | Correct | 1 ms | 6492 KB | Output is correct |

5 | Correct | 1 ms | 6492 KB | Output is correct |

6 | Correct | 1 ms | 6492 KB | Output is correct |

7 | Correct | 1 ms | 6492 KB | Output is correct |

8 | Correct | 1 ms | 6492 KB | Output is correct |

9 | Correct | 1 ms | 6568 KB | Output is correct |

10 | Correct | 1 ms | 6492 KB | Output is correct |

11 | Correct | 1 ms | 6492 KB | Output is correct |

12 | Correct | 1 ms | 6492 KB | Output is correct |

13 | Correct | 1 ms | 6488 KB | Output is correct |

14 | Correct | 1 ms | 6492 KB | Output is correct |

15 | Correct | 1 ms | 6596 KB | Output is correct |

16 | Correct | 1 ms | 6492 KB | Output is correct |

17 | Correct | 1 ms | 6488 KB | Output is correct |

18 | Correct | 1 ms | 6492 KB | Output is correct |

19 | Correct | 1 ms | 6492 KB | Output is correct |

20 | Correct | 2 ms | 6492 KB | Output is correct |

21 | Correct | 1 ms | 6492 KB | Output is correct |

22 | Correct | 1 ms | 6492 KB | Output is correct |

23 | Correct | 1 ms | 6492 KB | Output is correct |

24 | Correct | 1 ms | 6492 KB | Output is correct |

25 | Correct | 1 ms | 6488 KB | Output is correct |

26 | Correct | 1 ms | 6492 KB | Output is correct |

27 | Correct | 1 ms | 6492 KB | Output is correct |

28 | Correct | 2 ms | 6492 KB | Output is correct |

29 | Correct | 1 ms | 6492 KB | Output is correct |

30 | Correct | 2 ms | 6492 KB | Output is correct |

31 | Correct | 2 ms | 6492 KB | Output is correct |

32 | Correct | 1 ms | 6488 KB | Output is correct |

33 | Correct | 1 ms | 6488 KB | Output is correct |

34 | Correct | 1 ms | 6492 KB | Output is correct |

35 | Correct | 2 ms | 6492 KB | Output is correct |

36 | Correct | 7 ms | 7004 KB | Output is correct |

37 | Correct | 7 ms | 6748 KB | Output is correct |

38 | Correct | 4 ms | 6744 KB | Output is correct |

39 | Correct | 6 ms | 6492 KB | Output is correct |

40 | Correct | 6 ms | 6832 KB | Output is correct |

41 | Correct | 4 ms | 6744 KB | Output is correct |

42 | Correct | 87 ms | 9468 KB | Output is correct |

43 | Correct | 87 ms | 9688 KB | Output is correct |

44 | Correct | 38 ms | 9564 KB | Output is correct |

45 | Correct | 77 ms | 9088 KB | Output is correct |

46 | Correct | 70 ms | 9444 KB | Output is correct |

47 | Correct | 33 ms | 9304 KB | Output is correct |

48 | Correct | 66 ms | 9080 KB | Output is correct |

49 | Correct | 68 ms | 9296 KB | Output is correct |

50 | Correct | 28 ms | 9052 KB | Output is correct |

51 | Correct | 16 ms | 7772 KB | Output is correct |

52 | Correct | 66 ms | 9820 KB | Output is correct |

53 | Correct | 52 ms | 9552 KB | Output is correct |

54 | Correct | 64 ms | 7824 KB | Output is correct |

55 | Correct | 8 ms | 7004 KB | Output is correct |

56 | Correct | 8 ms | 6992 KB | Output is correct |

57 | Correct | 92 ms | 9920 KB | Output is correct |

58 | Correct | 53 ms | 8532 KB | Output is correct |

59 | Correct | 4 ms | 6996 KB | Output is correct |