# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
845652 | 2023-09-06T14:42:49 Z | ogkostya | Overtaking (IOI23_overtaking) | C++17 | 480 ms | 46960 KB |
#include "overtaking.h" #include <algorithm> #include <utility> #include <list> #include <climits> class Point { public: long long t, w; int i; }; struct sort1 { inline bool operator() (Point const& a, Point const& b) { if (a.t == b.t) return a.w < b.w; return a.t < b.t; } }; struct sort2 { inline bool operator() (Point const& a, Point const& b) { if (a.t == b.t) return b.w < a.w; return a.t < b.t; } }; int _M; std::vector<int> _S; int _X; std::vector<std::vector<long long>> arr; std::vector<std::vector<long long>> ans; void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) { _X = X; _M = M; _S = S; std::vector<Point> TW; TW.reserve(N); for (int i = 0; i < N; i++) { if (W[i] < X) continue; Point p = { T[i], W[i] }; TW.push_back(p); } if (TW.size() == 0) return; long long mb = 0; arr = std::vector<std::vector<long long>>(TW.size(), std::vector<long long>(M)); ans = std::vector<std::vector<long long>>(TW.size(), std::vector<long long>(M)); std::sort(TW.begin(), TW.end(), sort1()); for (int i = 0; i < TW.size(); i++) { arr[i][0] = TW[i].t; TW[i].i = i; } for (int j = 1; j < M; j++) { std::sort(TW.begin(), TW.end(), sort1()); mb = 0; for (int i = 0; i < TW.size(); i++) { long long a = TW[i].t; long long b = a + (_S[j] - _S[j - 1]) * TW[i].w; if (b < mb) b = mb; else mb = b; arr[i][j] = b; TW[i].t = b; } } for (int i = 0; i < TW.size(); i++) { ans[i][M - 1] = arr[i][M - 1]; } for (int j = M - 2; j >= 1; j--) { ans[0][j] = arr[0][j] + 1LL * (_S[M - 1] - _S[j]) * X; for (int i = 1; i < TW.size(); i++) { if (arr[i][j] == arr[i - 1][j]) { ans[i][j] = ans[i - 1][j]; } else { int ii = i - 1; int l = j; int r = arr[ii].size(); while (l < r) { int m = (l + r) / 2; long long c = arr[i][j] + 1LL * (_S[m] - _S[j]) * X; if (arr[ii][m] < c) { l = m + 1; } else { r = m; } } if (l < arr[ii].size()) { ans[i][j] = ans[ii][l]; } else { ans[i][j] = arr[i][j] + 1LL * (_S[M-1] - _S[j]) * X; } } } } } long long arrival_time(long long Y) { long long b = Y + 1LL * _S[_M - 1] * _X; if (arr.size() == 0) return b; int i = 0; if (arr[0][0] >= Y) return b; int l = 0, r = arr.size(); while (l < r) { int m = (l + r + 1) / 2; if (m == arr.size()) { break; } else if (arr[m][0] < Y) { l = m; } else { r = m - 1; } } i = l; l = 0; r = arr[i].size(); while (l < r) { int m = (l + r) / 2; long long c = Y + 1LL * _S[m] * _X; if (arr[i][m] < c) { l = m + 1; } else { r = m; } } if (l == arr[i].size()) return b; return ans[i][l]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 1 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 344 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 1 ms | 344 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 1 ms | 548 KB | Output is correct |
16 | Correct | 1 ms | 344 KB | Output is correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 1 ms | 344 KB | Output is correct |
21 | Correct | 0 ms | 344 KB | Output is correct |
22 | Correct | 1 ms | 344 KB | Output is correct |
23 | Correct | 1 ms | 344 KB | Output is correct |
24 | Correct | 1 ms | 344 KB | Output is correct |
25 | Correct | 1 ms | 344 KB | Output is correct |
26 | Correct | 1 ms | 344 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 0 ms | 344 KB | Output is correct |
29 | Correct | 0 ms | 344 KB | Output is correct |
30 | Correct | 0 ms | 344 KB | Output is correct |
31 | Correct | 0 ms | 344 KB | Output is correct |
32 | Correct | 1 ms | 344 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 344 KB | Output is correct |
35 | Correct | 1 ms | 344 KB | Output is correct |
36 | Correct | 0 ms | 348 KB | Output is correct |
37 | Correct | 0 ms | 344 KB | Output is correct |
38 | Correct | 0 ms | 344 KB | Output is correct |
39 | Correct | 0 ms | 348 KB | Output is correct |
40 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 1 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 1 ms | 344 KB | Output is correct |
13 | Correct | 0 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 344 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 1 ms | 344 KB | Output is correct |
21 | Correct | 1 ms | 344 KB | Output is correct |
22 | Correct | 1 ms | 548 KB | Output is correct |
23 | Correct | 1 ms | 344 KB | Output is correct |
24 | Correct | 1 ms | 344 KB | Output is correct |
25 | Correct | 1 ms | 344 KB | Output is correct |
26 | Correct | 1 ms | 344 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 0 ms | 344 KB | Output is correct |
29 | Correct | 1 ms | 344 KB | Output is correct |
30 | Correct | 1 ms | 344 KB | Output is correct |
31 | Correct | 1 ms | 344 KB | Output is correct |
32 | Correct | 1 ms | 344 KB | Output is correct |
33 | Correct | 1 ms | 344 KB | Output is correct |
34 | Correct | 1 ms | 344 KB | Output is correct |
35 | Correct | 0 ms | 344 KB | Output is correct |
36 | Correct | 0 ms | 344 KB | Output is correct |
37 | Correct | 0 ms | 344 KB | Output is correct |
38 | Correct | 0 ms | 344 KB | Output is correct |
39 | Correct | 1 ms | 344 KB | Output is correct |
40 | Correct | 1 ms | 348 KB | Output is correct |
41 | Correct | 1 ms | 344 KB | Output is correct |
42 | Correct | 1 ms | 344 KB | Output is correct |
43 | Correct | 0 ms | 348 KB | Output is correct |
44 | Correct | 0 ms | 344 KB | Output is correct |
45 | Correct | 0 ms | 344 KB | Output is correct |
46 | Correct | 0 ms | 348 KB | Output is correct |
47 | Correct | 0 ms | 348 KB | Output is correct |
48 | Correct | 64 ms | 16216 KB | Output is correct |
49 | Correct | 66 ms | 16216 KB | Output is correct |
50 | Correct | 73 ms | 16216 KB | Output is correct |
51 | Correct | 66 ms | 16216 KB | Output is correct |
52 | Correct | 69 ms | 16216 KB | Output is correct |
53 | Correct | 67 ms | 16216 KB | Output is correct |
54 | Correct | 69 ms | 16216 KB | Output is correct |
55 | Correct | 55 ms | 15960 KB | Output is correct |
56 | Correct | 57 ms | 16216 KB | Output is correct |
57 | Correct | 61 ms | 16216 KB | Output is correct |
58 | Correct | 62 ms | 16216 KB | Output is correct |
59 | Correct | 60 ms | 16216 KB | Output is correct |
60 | Correct | 57 ms | 16216 KB | Output is correct |
61 | Correct | 60 ms | 16236 KB | Output is correct |
62 | Correct | 2 ms | 600 KB | Output is correct |
63 | Correct | 2 ms | 600 KB | Output is correct |
64 | Correct | 29 ms | 8280 KB | Output is correct |
65 | Correct | 26 ms | 8536 KB | Output is correct |
66 | Correct | 49 ms | 16472 KB | Output is correct |
67 | Correct | 52 ms | 16216 KB | Output is correct |
68 | Correct | 51 ms | 16228 KB | Output is correct |
69 | Correct | 56 ms | 16216 KB | Output is correct |
70 | Correct | 67 ms | 16248 KB | Output is correct |
71 | Correct | 56 ms | 16216 KB | Output is correct |
72 | Correct | 83 ms | 16216 KB | Output is correct |
73 | Correct | 57 ms | 16244 KB | Output is correct |
74 | Correct | 59 ms | 16248 KB | Output is correct |
75 | Correct | 2 ms | 344 KB | Output is correct |
76 | Correct | 2 ms | 344 KB | Output is correct |
77 | Correct | 1 ms | 344 KB | Output is correct |
78 | Correct | 56 ms | 16216 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 344 KB | Output is correct |
7 | Correct | 1 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 344 KB | Output is correct |
12 | Correct | 1 ms | 344 KB | Output is correct |
13 | Correct | 0 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 344 KB | Output is correct |
16 | Correct | 0 ms | 344 KB | Output is correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 344 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 344 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 344 KB | Output is correct |
26 | Correct | 1 ms | 344 KB | Output is correct |
27 | Correct | 1 ms | 348 KB | Output is correct |
28 | Correct | 1 ms | 344 KB | Output is correct |
29 | Correct | 1 ms | 344 KB | Output is correct |
30 | Correct | 1 ms | 344 KB | Output is correct |
31 | Correct | 1 ms | 344 KB | Output is correct |
32 | Correct | 1 ms | 344 KB | Output is correct |
33 | Correct | 1 ms | 548 KB | Output is correct |
34 | Correct | 1 ms | 344 KB | Output is correct |
35 | Correct | 1 ms | 344 KB | Output is correct |
36 | Correct | 1 ms | 344 KB | Output is correct |
37 | Correct | 1 ms | 344 KB | Output is correct |
38 | Correct | 1 ms | 344 KB | Output is correct |
39 | Correct | 0 ms | 344 KB | Output is correct |
40 | Correct | 1 ms | 344 KB | Output is correct |
41 | Correct | 1 ms | 344 KB | Output is correct |
42 | Correct | 1 ms | 344 KB | Output is correct |
43 | Correct | 1 ms | 344 KB | Output is correct |
44 | Correct | 1 ms | 344 KB | Output is correct |
45 | Correct | 1 ms | 344 KB | Output is correct |
46 | Correct | 0 ms | 344 KB | Output is correct |
47 | Correct | 0 ms | 344 KB | Output is correct |
48 | Correct | 0 ms | 344 KB | Output is correct |
49 | Correct | 0 ms | 344 KB | Output is correct |
50 | Correct | 1 ms | 344 KB | Output is correct |
51 | Correct | 1 ms | 348 KB | Output is correct |
52 | Correct | 1 ms | 344 KB | Output is correct |
53 | Correct | 1 ms | 344 KB | Output is correct |
54 | Correct | 0 ms | 348 KB | Output is correct |
55 | Correct | 0 ms | 344 KB | Output is correct |
56 | Correct | 0 ms | 344 KB | Output is correct |
57 | Correct | 0 ms | 348 KB | Output is correct |
58 | Correct | 0 ms | 348 KB | Output is correct |
59 | Correct | 64 ms | 16216 KB | Output is correct |
60 | Correct | 66 ms | 16216 KB | Output is correct |
61 | Correct | 73 ms | 16216 KB | Output is correct |
62 | Correct | 66 ms | 16216 KB | Output is correct |
63 | Correct | 69 ms | 16216 KB | Output is correct |
64 | Correct | 67 ms | 16216 KB | Output is correct |
65 | Correct | 69 ms | 16216 KB | Output is correct |
66 | Correct | 55 ms | 15960 KB | Output is correct |
67 | Correct | 57 ms | 16216 KB | Output is correct |
68 | Correct | 61 ms | 16216 KB | Output is correct |
69 | Correct | 62 ms | 16216 KB | Output is correct |
70 | Correct | 60 ms | 16216 KB | Output is correct |
71 | Correct | 57 ms | 16216 KB | Output is correct |
72 | Correct | 60 ms | 16236 KB | Output is correct |
73 | Correct | 2 ms | 600 KB | Output is correct |
74 | Correct | 2 ms | 600 KB | Output is correct |
75 | Correct | 29 ms | 8280 KB | Output is correct |
76 | Correct | 26 ms | 8536 KB | Output is correct |
77 | Correct | 49 ms | 16472 KB | Output is correct |
78 | Correct | 52 ms | 16216 KB | Output is correct |
79 | Correct | 51 ms | 16228 KB | Output is correct |
80 | Correct | 56 ms | 16216 KB | Output is correct |
81 | Correct | 67 ms | 16248 KB | Output is correct |
82 | Correct | 56 ms | 16216 KB | Output is correct |
83 | Correct | 83 ms | 16216 KB | Output is correct |
84 | Correct | 57 ms | 16244 KB | Output is correct |
85 | Correct | 59 ms | 16248 KB | Output is correct |
86 | Correct | 2 ms | 344 KB | Output is correct |
87 | Correct | 2 ms | 344 KB | Output is correct |
88 | Correct | 1 ms | 344 KB | Output is correct |
89 | Correct | 56 ms | 16216 KB | Output is correct |
90 | Correct | 90 ms | 18516 KB | Output is correct |
91 | Correct | 294 ms | 42064 KB | Output is correct |
92 | Correct | 318 ms | 42060 KB | Output is correct |
93 | Correct | 296 ms | 42372 KB | Output is correct |
94 | Correct | 300 ms | 42504 KB | Output is correct |
95 | Correct | 296 ms | 42320 KB | Output is correct |
96 | Correct | 306 ms | 42576 KB | Output is correct |
97 | Correct | 76 ms | 18512 KB | Output is correct |
98 | Correct | 318 ms | 42148 KB | Output is correct |
99 | Correct | 317 ms | 42972 KB | Output is correct |
100 | Correct | 306 ms | 42060 KB | Output is correct |
101 | Correct | 306 ms | 42036 KB | Output is correct |
102 | Correct | 307 ms | 42332 KB | Output is correct |
103 | Correct | 305 ms | 42224 KB | Output is correct |
104 | Correct | 267 ms | 33652 KB | Output is correct |
105 | Correct | 294 ms | 36120 KB | Output is correct |
106 | Correct | 368 ms | 46960 KB | Output is correct |
107 | Correct | 358 ms | 46928 KB | Output is correct |
108 | Correct | 354 ms | 46848 KB | Output is correct |
109 | Correct | 368 ms | 46928 KB | Output is correct |
110 | Correct | 365 ms | 46928 KB | Output is correct |
111 | Correct | 328 ms | 42320 KB | Output is correct |
112 | Correct | 327 ms | 42304 KB | Output is correct |
113 | Correct | 386 ms | 43348 KB | Output is correct |
114 | Correct | 441 ms | 44676 KB | Output is correct |
115 | Correct | 376 ms | 43444 KB | Output is correct |
116 | Correct | 346 ms | 43604 KB | Output is correct |
117 | Correct | 169 ms | 29004 KB | Output is correct |
118 | Correct | 169 ms | 28992 KB | Output is correct |
119 | Correct | 163 ms | 27900 KB | Output is correct |
120 | Correct | 163 ms | 29072 KB | Output is correct |
121 | Correct | 163 ms | 30032 KB | Output is correct |
122 | Correct | 344 ms | 39128 KB | Output is correct |
123 | Correct | 447 ms | 44624 KB | Output is correct |
124 | Correct | 480 ms | 44608 KB | Output is correct |
125 | Correct | 455 ms | 44608 KB | Output is correct |