# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
617117 | 2022-08-01T08:48:15 Z | Je_O | Roller Coaster Railroad (IOI16_railroad) | C++17 | 210 ms | 24656 KB |
#include "railroad.h" #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; const int N = 2e5 + 5; int par[N]; int find(int x){ if(par[x] == x)return x; return par[x] = find(par[x]); } bool merge(int x, int y){ x = find(x); y = find(y); if(x == y)return false; par[x] = y; return true; } ll plan_roller_coaster(vector<int> s, vector<int> t){ int n = s.size(); s.pb(1e9); t.pb(1); vector<iii> v; for(int i = 0; i <= n; ++i){ v.pb(mp(s[i], mp(1, i))); v.pb(mp(t[i], mp(-1, i))); } sort(v.begin(), v.end()); for(int i = 0; i <= n; ++i)par[i] = i; vector<iii> lst; ll ans = 0, cur = 0; for(int i = 0; i < v.size() - 1; ++i){ cur += v[i].se.fi; ans += max(0LL, (ll)cur) * (v[i + 1].fi - v[i].fi); lst.pb(mp(v[i + 1].fi - v[i].fi, mp(v[i].se.se, v[i + 1].se.se))); if(v[i + 1].fi == v[i].fi || cur != 0){ merge(v[i].se.se, v[i + 1].se.se); } } sort(lst.begin(), lst.end()); for(int i = 0; i < lst.size(); ++i){ if(merge(lst[i].se.fi, lst[i].se.se)){ ans += lst[i].fi; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | n = 2 |
2 | Correct | 0 ms | 212 KB | n = 2 |
3 | Correct | 0 ms | 212 KB | n = 2 |
4 | Correct | 0 ms | 212 KB | n = 2 |
5 | Correct | 1 ms | 212 KB | n = 2 |
6 | Correct | 1 ms | 308 KB | n = 2 |
7 | Correct | 0 ms | 212 KB | n = 3 |
8 | Correct | 1 ms | 308 KB | n = 3 |
9 | Correct | 0 ms | 212 KB | n = 3 |
10 | Correct | 0 ms | 212 KB | n = 8 |
11 | Correct | 1 ms | 212 KB | n = 8 |
12 | Correct | 1 ms | 212 KB | n = 8 |
13 | Correct | 1 ms | 312 KB | n = 8 |
14 | Correct | 1 ms | 364 KB | n = 8 |
15 | Correct | 1 ms | 212 KB | n = 8 |
16 | Correct | 1 ms | 212 KB | n = 8 |
17 | Correct | 0 ms | 312 KB | n = 8 |
18 | Correct | 0 ms | 212 KB | n = 8 |
19 | Correct | 0 ms | 212 KB | n = 3 |
20 | Correct | 0 ms | 212 KB | n = 7 |
21 | Correct | 1 ms | 212 KB | n = 8 |
22 | Correct | 0 ms | 212 KB | n = 8 |
23 | Correct | 1 ms | 212 KB | n = 8 |
24 | Correct | 0 ms | 316 KB | n = 8 |
25 | Correct | 1 ms | 212 KB | n = 8 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | n = 2 |
2 | Correct | 0 ms | 212 KB | n = 2 |
3 | Correct | 0 ms | 212 KB | n = 2 |
4 | Correct | 0 ms | 212 KB | n = 2 |
5 | Correct | 1 ms | 212 KB | n = 2 |
6 | Correct | 1 ms | 308 KB | n = 2 |
7 | Correct | 0 ms | 212 KB | n = 3 |
8 | Correct | 1 ms | 308 KB | n = 3 |
9 | Correct | 0 ms | 212 KB | n = 3 |
10 | Correct | 0 ms | 212 KB | n = 8 |
11 | Correct | 1 ms | 212 KB | n = 8 |
12 | Correct | 1 ms | 212 KB | n = 8 |
13 | Correct | 1 ms | 312 KB | n = 8 |
14 | Correct | 1 ms | 364 KB | n = 8 |
15 | Correct | 1 ms | 212 KB | n = 8 |
16 | Correct | 1 ms | 212 KB | n = 8 |
17 | Correct | 0 ms | 312 KB | n = 8 |
18 | Correct | 0 ms | 212 KB | n = 8 |
19 | Correct | 0 ms | 212 KB | n = 3 |
20 | Correct | 0 ms | 212 KB | n = 7 |
21 | Correct | 1 ms | 212 KB | n = 8 |
22 | Correct | 0 ms | 212 KB | n = 8 |
23 | Correct | 1 ms | 212 KB | n = 8 |
24 | Correct | 0 ms | 316 KB | n = 8 |
25 | Correct | 1 ms | 212 KB | n = 8 |
26 | Correct | 1 ms | 212 KB | n = 8 |
27 | Correct | 1 ms | 308 KB | n = 8 |
28 | Correct | 0 ms | 212 KB | n = 8 |
29 | Correct | 0 ms | 212 KB | n = 16 |
30 | Correct | 1 ms | 212 KB | n = 16 |
31 | Correct | 0 ms | 312 KB | n = 16 |
32 | Correct | 1 ms | 312 KB | n = 16 |
33 | Correct | 1 ms | 312 KB | n = 16 |
34 | Correct | 0 ms | 212 KB | n = 16 |
35 | Correct | 1 ms | 212 KB | n = 16 |
36 | Correct | 1 ms | 212 KB | n = 15 |
37 | Correct | 1 ms | 212 KB | n = 8 |
38 | Correct | 0 ms | 212 KB | n = 16 |
39 | Correct | 0 ms | 212 KB | n = 16 |
40 | Correct | 1 ms | 212 KB | n = 9 |
41 | Correct | 1 ms | 212 KB | n = 16 |
42 | Correct | 1 ms | 212 KB | n = 16 |
43 | Correct | 1 ms | 312 KB | n = 16 |
44 | Correct | 1 ms | 212 KB | n = 9 |
45 | Correct | 1 ms | 212 KB | n = 15 |
46 | Correct | 1 ms | 308 KB | n = 16 |
47 | Correct | 1 ms | 212 KB | n = 16 |
48 | Correct | 1 ms | 212 KB | n = 16 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 177 ms | 21940 KB | n = 199999 |
2 | Correct | 154 ms | 21916 KB | n = 199991 |
3 | Correct | 156 ms | 21920 KB | n = 199993 |
4 | Correct | 137 ms | 18736 KB | n = 152076 |
5 | Correct | 76 ms | 10644 KB | n = 93249 |
6 | Correct | 151 ms | 20864 KB | n = 199910 |
7 | Correct | 147 ms | 21312 KB | n = 199999 |
8 | Correct | 164 ms | 20892 KB | n = 199997 |
9 | Correct | 139 ms | 20092 KB | n = 171294 |
10 | Correct | 114 ms | 18236 KB | n = 140872 |
11 | Correct | 145 ms | 20900 KB | n = 199886 |
12 | Correct | 151 ms | 21352 KB | n = 199996 |
13 | Correct | 146 ms | 20900 KB | n = 200000 |
14 | Correct | 148 ms | 21156 KB | n = 199998 |
15 | Correct | 153 ms | 21136 KB | n = 200000 |
16 | Correct | 169 ms | 21492 KB | n = 199998 |
17 | Correct | 156 ms | 24560 KB | n = 200000 |
18 | Correct | 153 ms | 21500 KB | n = 190000 |
19 | Correct | 132 ms | 22848 KB | n = 177777 |
20 | Correct | 70 ms | 11172 KB | n = 100000 |
21 | Correct | 210 ms | 21972 KB | n = 200000 |
22 | Correct | 196 ms | 22040 KB | n = 200000 |
23 | Correct | 160 ms | 22004 KB | n = 200000 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | n = 2 |
2 | Correct | 0 ms | 212 KB | n = 2 |
3 | Correct | 0 ms | 212 KB | n = 2 |
4 | Correct | 0 ms | 212 KB | n = 2 |
5 | Correct | 1 ms | 212 KB | n = 2 |
6 | Correct | 1 ms | 308 KB | n = 2 |
7 | Correct | 0 ms | 212 KB | n = 3 |
8 | Correct | 1 ms | 308 KB | n = 3 |
9 | Correct | 0 ms | 212 KB | n = 3 |
10 | Correct | 0 ms | 212 KB | n = 8 |
11 | Correct | 1 ms | 212 KB | n = 8 |
12 | Correct | 1 ms | 212 KB | n = 8 |
13 | Correct | 1 ms | 312 KB | n = 8 |
14 | Correct | 1 ms | 364 KB | n = 8 |
15 | Correct | 1 ms | 212 KB | n = 8 |
16 | Correct | 1 ms | 212 KB | n = 8 |
17 | Correct | 0 ms | 312 KB | n = 8 |
18 | Correct | 0 ms | 212 KB | n = 8 |
19 | Correct | 0 ms | 212 KB | n = 3 |
20 | Correct | 0 ms | 212 KB | n = 7 |
21 | Correct | 1 ms | 212 KB | n = 8 |
22 | Correct | 0 ms | 212 KB | n = 8 |
23 | Correct | 1 ms | 212 KB | n = 8 |
24 | Correct | 0 ms | 316 KB | n = 8 |
25 | Correct | 1 ms | 212 KB | n = 8 |
26 | Correct | 1 ms | 212 KB | n = 8 |
27 | Correct | 1 ms | 308 KB | n = 8 |
28 | Correct | 0 ms | 212 KB | n = 8 |
29 | Correct | 0 ms | 212 KB | n = 16 |
30 | Correct | 1 ms | 212 KB | n = 16 |
31 | Correct | 0 ms | 312 KB | n = 16 |
32 | Correct | 1 ms | 312 KB | n = 16 |
33 | Correct | 1 ms | 312 KB | n = 16 |
34 | Correct | 0 ms | 212 KB | n = 16 |
35 | Correct | 1 ms | 212 KB | n = 16 |
36 | Correct | 1 ms | 212 KB | n = 15 |
37 | Correct | 1 ms | 212 KB | n = 8 |
38 | Correct | 0 ms | 212 KB | n = 16 |
39 | Correct | 0 ms | 212 KB | n = 16 |
40 | Correct | 1 ms | 212 KB | n = 9 |
41 | Correct | 1 ms | 212 KB | n = 16 |
42 | Correct | 1 ms | 212 KB | n = 16 |
43 | Correct | 1 ms | 312 KB | n = 16 |
44 | Correct | 1 ms | 212 KB | n = 9 |
45 | Correct | 1 ms | 212 KB | n = 15 |
46 | Correct | 1 ms | 308 KB | n = 16 |
47 | Correct | 1 ms | 212 KB | n = 16 |
48 | Correct | 1 ms | 212 KB | n = 16 |
49 | Correct | 177 ms | 21940 KB | n = 199999 |
50 | Correct | 154 ms | 21916 KB | n = 199991 |
51 | Correct | 156 ms | 21920 KB | n = 199993 |
52 | Correct | 137 ms | 18736 KB | n = 152076 |
53 | Correct | 76 ms | 10644 KB | n = 93249 |
54 | Correct | 151 ms | 20864 KB | n = 199910 |
55 | Correct | 147 ms | 21312 KB | n = 199999 |
56 | Correct | 164 ms | 20892 KB | n = 199997 |
57 | Correct | 139 ms | 20092 KB | n = 171294 |
58 | Correct | 114 ms | 18236 KB | n = 140872 |
59 | Correct | 145 ms | 20900 KB | n = 199886 |
60 | Correct | 151 ms | 21352 KB | n = 199996 |
61 | Correct | 146 ms | 20900 KB | n = 200000 |
62 | Correct | 148 ms | 21156 KB | n = 199998 |
63 | Correct | 153 ms | 21136 KB | n = 200000 |
64 | Correct | 169 ms | 21492 KB | n = 199998 |
65 | Correct | 156 ms | 24560 KB | n = 200000 |
66 | Correct | 153 ms | 21500 KB | n = 190000 |
67 | Correct | 132 ms | 22848 KB | n = 177777 |
68 | Correct | 70 ms | 11172 KB | n = 100000 |
69 | Correct | 210 ms | 21972 KB | n = 200000 |
70 | Correct | 196 ms | 22040 KB | n = 200000 |
71 | Correct | 160 ms | 22004 KB | n = 200000 |
72 | Correct | 182 ms | 21996 KB | n = 200000 |
73 | Correct | 179 ms | 22032 KB | n = 200000 |
74 | Correct | 175 ms | 22024 KB | n = 200000 |
75 | Correct | 164 ms | 21904 KB | n = 200000 |
76 | Correct | 148 ms | 21996 KB | n = 200000 |
77 | Correct | 148 ms | 22000 KB | n = 200000 |
78 | Correct | 153 ms | 21924 KB | n = 200000 |
79 | Correct | 167 ms | 20852 KB | n = 184307 |
80 | Correct | 58 ms | 9616 KB | n = 76040 |
81 | Correct | 165 ms | 20896 KB | n = 199981 |
82 | Correct | 153 ms | 21352 KB | n = 199994 |
83 | Correct | 156 ms | 20892 KB | n = 199996 |
84 | Correct | 146 ms | 21108 KB | n = 199998 |
85 | Correct | 174 ms | 21164 KB | n = 200000 |
86 | Correct | 161 ms | 21524 KB | n = 199998 |
87 | Correct | 148 ms | 24656 KB | n = 200000 |
88 | Correct | 154 ms | 22492 KB | n = 200000 |
89 | Correct | 140 ms | 24596 KB | n = 200000 |
90 | Correct | 156 ms | 21996 KB | n = 200000 |
91 | Correct | 154 ms | 22004 KB | n = 200000 |
92 | Correct | 154 ms | 21920 KB | n = 200000 |