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

159567 | 2019-10-23T09:54:25 Z | geon040702 | None (KOI16_dd) | C++14 | 145 ms | 12920 KB |

#include <bits/stdc++.h> #define MAX 999999999 using namespace std; struct Item { int x, y[2]; bool operator<(const Item &r) const { return x < r.x; } }; int n, start_y, end_x; Item hurdle[100010]; set< pair<int,int> > data1; int data2[100010]; void calc_route() { int i, j, temp[2]; int ans = MAX, cnt = 0; set< pair<int, int> >::iterator pos, st, ed; data1.insert(make_pair(start_y, 0)); for(i = 1 ; i <= n ; i++) { temp[0] = temp[1] = MAX; st = data1.lower_bound(make_pair(hurdle[i].y[0], 0)); ed = data1.upper_bound(make_pair(hurdle[i].y[1], MAX)); for(pos = st; pos != ed ; ++pos) for(j = 0 ; j <= 1 ; j++) temp[j] = min(temp[j], (*pos).second + abs(hurdle[i].y[j] - (*pos).first)); data1.erase(st, ed); for(j = 0 ; j <= 1 ; j++) data1.insert(make_pair(hurdle[i].y[j], temp[j])); } for(pos = data1.begin(); pos != data1.end(); ++pos) { if(ans > (*pos).second) { ans = (*pos).second; cnt = 0; } if(ans == (*pos).second) data2[cnt++] = (*pos).first; } printf("%d\n%d", ans + end_x, cnt); for(i = 0 ; i < cnt ; i++) printf(" %d", data2[i]); } int main(void) { int i; scanf("%d %d %d", &n, &start_y, &end_x); for(i = 1 ; i <= n ; i++) { scanf("%d %d %d", &hurdle[i].x, &hurdle[i].y[0], &hurdle[i].y[1]); } sort(hurdle+1, hurdle+n+1); calc_route(); return 0; }

### Compilation message

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

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

2 | Correct | 2 ms | 256 KB | Output is correct |

3 | Correct | 2 ms | 256 KB | Output is correct |

4 | Correct | 2 ms | 256 KB | Output is correct |

5 | Correct | 2 ms | 376 KB | Output is correct |

6 | Correct | 2 ms | 376 KB | Output is correct |

7 | Correct | 2 ms | 256 KB | Output is correct |

8 | Correct | 2 ms | 376 KB | Output is correct |

9 | Correct | 2 ms | 244 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 2 ms | 376 KB | Output is correct |

12 | Correct | 2 ms | 376 KB | Output is correct |

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

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

2 | Correct | 2 ms | 256 KB | Output is correct |

3 | Correct | 2 ms | 256 KB | Output is correct |

4 | Correct | 2 ms | 256 KB | Output is correct |

5 | Correct | 2 ms | 376 KB | Output is correct |

6 | Correct | 2 ms | 376 KB | Output is correct |

7 | Correct | 2 ms | 256 KB | Output is correct |

8 | Correct | 2 ms | 376 KB | Output is correct |

9 | Correct | 2 ms | 244 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 2 ms | 376 KB | Output is correct |

12 | Correct | 2 ms | 376 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 376 KB | Output is correct |

15 | Correct | 2 ms | 376 KB | Output is correct |

16 | Correct | 2 ms | 376 KB | Output is correct |

17 | Correct | 3 ms | 376 KB | Output is correct |

18 | Correct | 3 ms | 376 KB | Output is correct |

19 | Correct | 3 ms | 376 KB | Output is correct |

20 | Correct | 3 ms | 408 KB | Output is correct |

21 | Correct | 2 ms | 376 KB | Output is correct |

22 | Correct | 2 ms | 376 KB | Output is correct |

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

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

2 | Correct | 2 ms | 256 KB | Output is correct |

3 | Correct | 2 ms | 256 KB | Output is correct |

4 | Correct | 2 ms | 256 KB | Output is correct |

5 | Correct | 2 ms | 376 KB | Output is correct |

6 | Correct | 2 ms | 376 KB | Output is correct |

7 | Correct | 2 ms | 256 KB | Output is correct |

8 | Correct | 2 ms | 376 KB | Output is correct |

9 | Correct | 2 ms | 244 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 2 ms | 376 KB | Output is correct |

12 | Correct | 2 ms | 376 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 376 KB | Output is correct |

15 | Correct | 2 ms | 376 KB | Output is correct |

16 | Correct | 2 ms | 376 KB | Output is correct |

17 | Correct | 3 ms | 376 KB | Output is correct |

18 | Correct | 3 ms | 376 KB | Output is correct |

19 | Correct | 3 ms | 376 KB | Output is correct |

20 | Correct | 3 ms | 408 KB | Output is correct |

21 | Correct | 2 ms | 376 KB | Output is correct |

22 | Correct | 2 ms | 376 KB | Output is correct |

23 | Correct | 2 ms | 376 KB | Output is correct |

24 | Correct | 2 ms | 256 KB | Output is correct |

25 | Correct | 2 ms | 376 KB | Output is correct |

26 | Correct | 3 ms | 376 KB | Output is correct |

27 | Correct | 2 ms | 376 KB | Output is correct |

28 | Correct | 3 ms | 376 KB | Output is correct |

29 | Correct | 4 ms | 376 KB | Output is correct |

30 | Correct | 3 ms | 376 KB | Output is correct |

31 | Correct | 3 ms | 376 KB | Output is correct |

32 | Correct | 3 ms | 376 KB | Output is correct |

33 | Correct | 2 ms | 376 KB | Output is correct |

34 | Correct | 2 ms | 376 KB | Output is correct |

35 | Correct | 3 ms | 376 KB | Output is correct |

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

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

2 | Correct | 2 ms | 256 KB | Output is correct |

3 | Correct | 2 ms | 256 KB | Output is correct |

4 | Correct | 2 ms | 256 KB | Output is correct |

5 | Correct | 2 ms | 376 KB | Output is correct |

6 | Correct | 2 ms | 376 KB | Output is correct |

7 | Correct | 2 ms | 256 KB | Output is correct |

8 | Correct | 2 ms | 376 KB | Output is correct |

9 | Correct | 2 ms | 244 KB | Output is correct |

10 | Correct | 2 ms | 376 KB | Output is correct |

11 | Correct | 2 ms | 376 KB | Output is correct |

12 | Correct | 2 ms | 376 KB | Output is correct |

13 | Correct | 2 ms | 376 KB | Output is correct |

14 | Correct | 2 ms | 376 KB | Output is correct |

15 | Correct | 2 ms | 376 KB | Output is correct |

16 | Correct | 2 ms | 376 KB | Output is correct |

17 | Correct | 3 ms | 376 KB | Output is correct |

18 | Correct | 3 ms | 376 KB | Output is correct |

19 | Correct | 3 ms | 376 KB | Output is correct |

20 | Correct | 3 ms | 408 KB | Output is correct |

21 | Correct | 2 ms | 376 KB | Output is correct |

22 | Correct | 2 ms | 376 KB | Output is correct |

23 | Correct | 2 ms | 376 KB | Output is correct |

24 | Correct | 2 ms | 256 KB | Output is correct |

25 | Correct | 2 ms | 376 KB | Output is correct |

26 | Correct | 3 ms | 376 KB | Output is correct |

27 | Correct | 2 ms | 376 KB | Output is correct |

28 | Correct | 3 ms | 376 KB | Output is correct |

29 | Correct | 4 ms | 376 KB | Output is correct |

30 | Correct | 3 ms | 376 KB | Output is correct |

31 | Correct | 3 ms | 376 KB | Output is correct |

32 | Correct | 3 ms | 376 KB | Output is correct |

33 | Correct | 2 ms | 376 KB | Output is correct |

34 | Correct | 2 ms | 376 KB | Output is correct |

35 | Correct | 3 ms | 376 KB | Output is correct |

36 | Correct | 9 ms | 628 KB | Output is correct |

37 | Correct | 9 ms | 504 KB | Output is correct |

38 | Correct | 7 ms | 504 KB | Output is correct |

39 | Correct | 9 ms | 504 KB | Output is correct |

40 | Correct | 8 ms | 508 KB | Output is correct |

41 | Correct | 7 ms | 504 KB | Output is correct |

42 | Correct | 89 ms | 3704 KB | Output is correct |

43 | Correct | 88 ms | 3576 KB | Output is correct |

44 | Correct | 65 ms | 3320 KB | Output is correct |

45 | Correct | 79 ms | 3192 KB | Output is correct |

46 | Correct | 78 ms | 3124 KB | Output is correct |

47 | Correct | 55 ms | 2944 KB | Output is correct |

48 | Correct | 70 ms | 2936 KB | Output is correct |

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

50 | Correct | 49 ms | 2524 KB | Output is correct |

51 | Correct | 34 ms | 3192 KB | Output is correct |

52 | Correct | 56 ms | 3576 KB | Output is correct |

53 | Correct | 145 ms | 12920 KB | Output is correct |

54 | Correct | 53 ms | 3704 KB | Output is correct |

55 | Correct | 10 ms | 632 KB | Output is correct |

56 | Correct | 10 ms | 632 KB | Output is correct |

57 | Correct | 83 ms | 3576 KB | Output is correct |

58 | Correct | 109 ms | 8284 KB | Output is correct |

59 | Correct | 8 ms | 632 KB | Output is correct |