oj.uz

Submission #96873

# Submission time Handle Problem Language Result Execution time Memory
96873 2019-02-12T14:36:27 Z youngyojun Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 294 ms 17044 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

const int MAXN = 200055;

int ud[MAXN*2], C[MAXN*2], O[MAXN*2];

vector<int> XV;
int A[MAXN], B[MAXN], AI[MAXN], BI[MAXN];

ll Ans;
int N, K;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

ll getAns() {
	XV.eb(0); XV.eb(INF);
	for(int i = 0; i < N; i++) {
		XV.eb(A[i]);
		XV.eb(B[i]);
	}
	sorv(XV); univ(XV); K = sz(XV);
	iota(ud, ud+K, 0);
	for(int i = 0; i < N; i++) {
		AI[i] = int(lower_bound(allv(XV), A[i]) - XV.begin());
		BI[i] = int(lower_bound(allv(XV), B[i]) - XV.begin());
		C[AI[i]]--; C[BI[i]]++;
		uf(AI[i], BI[i]);
	}
	C[0] = -1; C[1]++; uf(0, 1);
	for(int i = 2; i < K; i++) if(C[i-1]) {
		uf(i-1, i);
		if(C[i-1] < 0) Ans -= ll(C[i-1]) * (XV[i]-XV[i-1]);
		C[i] += C[i-1]; C[i-1] = 0;
	}
	iota(O, O+K, 0); sort(O+1, O+K, [&](int a, int b) {
		return XV[a]-XV[a-1] < XV[b]-XV[b-1];
	});
	for(int oi = 1, i; oi < K; oi++) {
		i = O[oi];
		if(uf(i-1) == uf(i)) continue;
		Ans += XV[i] - XV[i-1];
		uf(i-1, i);
	}
	return Ans;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	::N = sz(s);
	for(int i = 0; i < N; i++) {
		::A[i] = s[i];
		::B[i] = t[i];
	}
	return getAns();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 4 ms 384 KB n = 3
8 Correct 3 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 3 ms 384 KB n = 8
11 Correct 3 ms 384 KB n = 8
12 Correct 3 ms 384 KB n = 8
13 Correct 3 ms 384 KB n = 8
14 Correct 3 ms 384 KB n = 8
15 Correct 3 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 3 ms 384 KB n = 8
18 Correct 3 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 3 ms 384 KB n = 8
22 Correct 3 ms 384 KB n = 8
23 Correct 3 ms 384 KB n = 8
24 Correct 3 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 4 ms 384 KB n = 3
8 Correct 3 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 3 ms 384 KB n = 8
11 Correct 3 ms 384 KB n = 8
12 Correct 3 ms 384 KB n = 8
13 Correct 3 ms 384 KB n = 8
14 Correct 3 ms 384 KB n = 8
15 Correct 3 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 3 ms 384 KB n = 8
18 Correct 3 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 3 ms 384 KB n = 8
22 Correct 3 ms 384 KB n = 8
23 Correct 3 ms 384 KB n = 8
24 Correct 3 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 384 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 3 ms 384 KB n = 8
29 Correct 3 ms 384 KB n = 16
30 Correct 2 ms 380 KB n = 16
31 Correct 2 ms 384 KB n = 16
32 Correct 2 ms 356 KB n = 16
33 Correct 3 ms 384 KB n = 16
34 Correct 2 ms 384 KB n = 16
35 Correct 3 ms 384 KB n = 16
36 Correct 2 ms 384 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 3 ms 384 KB n = 16
39 Correct 2 ms 384 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 2 ms 384 KB n = 16
42 Correct 3 ms 384 KB n = 16
43 Correct 2 ms 384 KB n = 16
44 Correct 4 ms 384 KB n = 9
45 Correct 2 ms 384 KB n = 15
46 Correct 2 ms 384 KB n = 16
47 Correct 2 ms 428 KB n = 16
48 Correct 3 ms 384 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 13032 KB n = 199999
2 Correct 290 ms 13136 KB n = 199991
3 Correct 274 ms 13160 KB n = 199993
4 Correct 185 ms 10052 KB n = 152076
5 Correct 123 ms 6380 KB n = 93249
6 Correct 217 ms 12296 KB n = 199910
7 Correct 249 ms 12940 KB n = 199999
8 Correct 212 ms 12136 KB n = 199997
9 Correct 201 ms 11384 KB n = 171294
10 Correct 176 ms 9320 KB n = 140872
11 Correct 196 ms 12364 KB n = 199886
12 Correct 230 ms 13160 KB n = 199996
13 Correct 189 ms 12392 KB n = 200000
14 Correct 268 ms 13352 KB n = 199998
15 Correct 257 ms 13216 KB n = 200000
16 Correct 249 ms 13416 KB n = 199998
17 Correct 258 ms 13032 KB n = 200000
18 Correct 248 ms 12556 KB n = 190000
19 Correct 188 ms 11624 KB n = 177777
20 Correct 134 ms 6892 KB n = 100000
21 Correct 248 ms 13032 KB n = 200000
22 Correct 290 ms 13032 KB n = 200000
23 Correct 269 ms 13148 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 384 KB n = 2
3 Correct 2 ms 384 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 4 ms 384 KB n = 3
8 Correct 3 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 3 ms 384 KB n = 8
11 Correct 3 ms 384 KB n = 8
12 Correct 3 ms 384 KB n = 8
13 Correct 3 ms 384 KB n = 8
14 Correct 3 ms 384 KB n = 8
15 Correct 3 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 3 ms 384 KB n = 8
18 Correct 3 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 3 ms 384 KB n = 8
22 Correct 3 ms 384 KB n = 8
23 Correct 3 ms 384 KB n = 8
24 Correct 3 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 384 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 3 ms 384 KB n = 8
29 Correct 3 ms 384 KB n = 16
30 Correct 2 ms 380 KB n = 16
31 Correct 2 ms 384 KB n = 16
32 Correct 2 ms 356 KB n = 16
33 Correct 3 ms 384 KB n = 16
34 Correct 2 ms 384 KB n = 16
35 Correct 3 ms 384 KB n = 16
36 Correct 2 ms 384 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 3 ms 384 KB n = 16
39 Correct 2 ms 384 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 2 ms 384 KB n = 16
42 Correct 3 ms 384 KB n = 16
43 Correct 2 ms 384 KB n = 16
44 Correct 4 ms 384 KB n = 9
45 Correct 2 ms 384 KB n = 15
46 Correct 2 ms 384 KB n = 16
47 Correct 2 ms 428 KB n = 16
48 Correct 3 ms 384 KB n = 16
49 Correct 229 ms 13032 KB n = 199999
50 Correct 290 ms 13136 KB n = 199991
51 Correct 274 ms 13160 KB n = 199993
52 Correct 185 ms 10052 KB n = 152076
53 Correct 123 ms 6380 KB n = 93249
54 Correct 217 ms 12296 KB n = 199910
55 Correct 249 ms 12940 KB n = 199999
56 Correct 212 ms 12136 KB n = 199997
57 Correct 201 ms 11384 KB n = 171294
58 Correct 176 ms 9320 KB n = 140872
59 Correct 196 ms 12364 KB n = 199886
60 Correct 230 ms 13160 KB n = 199996
61 Correct 189 ms 12392 KB n = 200000
62 Correct 268 ms 13352 KB n = 199998
63 Correct 257 ms 13216 KB n = 200000
64 Correct 249 ms 13416 KB n = 199998
65 Correct 258 ms 13032 KB n = 200000
66 Correct 248 ms 12556 KB n = 190000
67 Correct 188 ms 11624 KB n = 177777
68 Correct 134 ms 6892 KB n = 100000
69 Correct 248 ms 13032 KB n = 200000
70 Correct 290 ms 13032 KB n = 200000
71 Correct 269 ms 13148 KB n = 200000
72 Correct 272 ms 16944 KB n = 200000
73 Correct 283 ms 17044 KB n = 200000
74 Correct 276 ms 16804 KB n = 200000
75 Correct 276 ms 17004 KB n = 200000
76 Correct 277 ms 17000 KB n = 200000
77 Correct 207 ms 14696 KB n = 200000
78 Correct 215 ms 14632 KB n = 200000
79 Correct 230 ms 15552 KB n = 184307
80 Correct 80 ms 6764 KB n = 76040
81 Correct 182 ms 15084 KB n = 199981
82 Correct 241 ms 16360 KB n = 199994
83 Correct 178 ms 15208 KB n = 199996
84 Correct 218 ms 16360 KB n = 199998
85 Correct 218 ms 16204 KB n = 200000
86 Correct 218 ms 16872 KB n = 199998
87 Correct 294 ms 16924 KB n = 200000
88 Correct 261 ms 17000 KB n = 200000
89 Correct 282 ms 16924 KB n = 200000
90 Correct 279 ms 17000 KB n = 200000
91 Correct 271 ms 16916 KB n = 200000
92 Correct 293 ms 17004 KB n = 200000