oj.uz

Submission #65962

# Submission time Handle Problem Language Result Execution time Memory
65962 2018-08-09T07:44:05 Z gs13068 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 319 ms 158168 KB 
#include "railroad.h"
#include <algorithm>
 
using namespace std;
 
int x[400004], xn;
int a[400004];
int p[400004];
pair<int, pair<int, int> > d[400004];
int dn;
 
int f(int x) {
    return x == p[x] ? x : p[x] = f(p[x]);
}
 
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    long long r = 0;
    int n = (int) s.size();
    int i;
    for (i = 0; i < n; i++) {
        x[xn++] = s[i];
        x[xn++] = t[i];
    }
    sort(x, x + xn);
    xn = unique(x, x + xn) - x;
    for (i = 0; i <= xn; i++) p[i] = i;
    for (i = 0; i < n; i++) {
        s[i] = lower_bound(x, x + xn, s[i]) - x;
        t[i] = lower_bound(x, x + xn, t[i]) - x;
        a[s[i]]++, a[t[i]]--;
        p[f(s[i])] = f(t[i]);
    }
    for (i = 0; i < xn; i++) {
        a[i + 1] += a[i];
        if (a[i] != 1) {
            p[f(i)] = f(i + 1);
            if (a[i] > 1) r += (a[i] - 1ll) * (x[i + 1] - x[i]);
        }
        else {
            d[dn].first = x[i + 1] - x[i];
            d[dn].second.first = i;
            d[dn].second.second = i + 1;
            dn++;
        }
    }
    sort(d, d + dn);
    for (i = 0; i < dn; i++) if (f(d[i].second.first) != f(d[i].second.second)) {
        r += d[i].first;
        p[f(d[i].second.first)] = d[i].second.second;
    }
    return r;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 3 ms 608 KB n = 2
4 Correct 3 ms 608 KB n = 2
5 Correct 2 ms 608 KB n = 2
6 Correct 2 ms 692 KB n = 2
7 Correct 4 ms 824 KB n = 3
8 Correct 2 ms 824 KB n = 3
9 Correct 3 ms 824 KB n = 3
10 Correct 3 ms 824 KB n = 8
11 Correct 3 ms 824 KB n = 8
12 Correct 3 ms 824 KB n = 8
13 Correct 3 ms 824 KB n = 8
14 Correct 3 ms 824 KB n = 8
15 Correct 3 ms 824 KB n = 8
16 Correct 2 ms 824 KB n = 8
17 Correct 2 ms 824 KB n = 8
18 Correct 2 ms 824 KB n = 8
19 Correct 3 ms 824 KB n = 3
20 Correct 3 ms 824 KB n = 7
21 Correct 3 ms 824 KB n = 8
22 Correct 3 ms 824 KB n = 8
23 Correct 2 ms 824 KB n = 8
24 Correct 2 ms 824 KB n = 8
25 Correct 3 ms 828 KB n = 8
26 Correct 3 ms 832 KB n = 8
27 Correct 2 ms 832 KB n = 8
28 Correct 2 ms 840 KB n = 8
29 Correct 3 ms 844 KB n = 16
30 Correct 3 ms 852 KB n = 16
31 Correct 2 ms 856 KB n = 16
32 Correct 2 ms 860 KB n = 16
33 Correct 3 ms 864 KB n = 16
34 Correct 3 ms 868 KB n = 16
35 Correct 3 ms 872 KB n = 16
36 Correct 2 ms 872 KB n = 15
37 Correct 2 ms 880 KB n = 8
38 Correct 2 ms 884 KB n = 16
39 Correct 2 ms 888 KB n = 16
40 Correct 3 ms 892 KB n = 9
41 Correct 2 ms 896 KB n = 16
42 Correct 2 ms 900 KB n = 16
43 Correct 3 ms 900 KB n = 16
44 Correct 3 ms 900 KB n = 9
45 Correct 3 ms 992 KB n = 15
46 Correct 2 ms 992 KB n = 16
47 Correct 2 ms 992 KB n = 16
48 Correct 2 ms 992 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 12712 KB n = 199999
2 Correct 230 ms 16496 KB n = 199991
3 Correct 242 ms 20488 KB n = 199993
4 Correct 167 ms 21168 KB n = 152076
5 Correct 106 ms 21168 KB n = 93249
6 Correct 207 ms 27056 KB n = 199910
7 Correct 202 ms 30676 KB n = 199999
8 Correct 205 ms 32880 KB n = 199997
9 Correct 204 ms 35560 KB n = 171294
10 Correct 159 ms 37032 KB n = 140872
11 Correct 204 ms 41784 KB n = 199886
12 Correct 185 ms 46068 KB n = 199996
13 Correct 189 ms 48672 KB n = 200000
14 Correct 210 ms 54596 KB n = 199998
15 Correct 218 ms 57164 KB n = 200000
16 Correct 227 ms 60480 KB n = 199998
17 Correct 201 ms 64780 KB n = 200000
18 Correct 199 ms 65180 KB n = 190000
19 Correct 244 ms 70596 KB n = 177777
20 Correct 127 ms 70596 KB n = 100000
21 Correct 257 ms 74452 KB n = 200000
22 Correct 256 ms 80648 KB n = 200000
23 Correct 238 ms 84508 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 3 ms 608 KB n = 2
4 Correct 3 ms 608 KB n = 2
5 Correct 2 ms 608 KB n = 2
6 Correct 2 ms 692 KB n = 2
7 Correct 4 ms 824 KB n = 3
8 Correct 2 ms 824 KB n = 3
9 Correct 3 ms 824 KB n = 3
10 Correct 3 ms 824 KB n = 8
11 Correct 3 ms 824 KB n = 8
12 Correct 3 ms 824 KB n = 8
13 Correct 3 ms 824 KB n = 8
14 Correct 3 ms 824 KB n = 8
15 Correct 3 ms 824 KB n = 8
16 Correct 2 ms 824 KB n = 8
17 Correct 2 ms 824 KB n = 8
18 Correct 2 ms 824 KB n = 8
19 Correct 3 ms 824 KB n = 3
20 Correct 3 ms 824 KB n = 7
21 Correct 3 ms 824 KB n = 8
22 Correct 3 ms 824 KB n = 8
23 Correct 2 ms 824 KB n = 8
24 Correct 2 ms 824 KB n = 8
25 Correct 3 ms 828 KB n = 8
26 Correct 3 ms 832 KB n = 8
27 Correct 2 ms 832 KB n = 8
28 Correct 2 ms 840 KB n = 8
29 Correct 3 ms 844 KB n = 16
30 Correct 3 ms 852 KB n = 16
31 Correct 2 ms 856 KB n = 16
32 Correct 2 ms 860 KB n = 16
33 Correct 3 ms 864 KB n = 16
34 Correct 3 ms 868 KB n = 16
35 Correct 3 ms 872 KB n = 16
36 Correct 2 ms 872 KB n = 15
37 Correct 2 ms 880 KB n = 8
38 Correct 2 ms 884 KB n = 16
39 Correct 2 ms 888 KB n = 16
40 Correct 3 ms 892 KB n = 9
41 Correct 2 ms 896 KB n = 16
42 Correct 2 ms 900 KB n = 16
43 Correct 3 ms 900 KB n = 16
44 Correct 3 ms 900 KB n = 9
45 Correct 3 ms 992 KB n = 15
46 Correct 2 ms 992 KB n = 16
47 Correct 2 ms 992 KB n = 16
48 Correct 2 ms 992 KB n = 16
49 Correct 238 ms 12712 KB n = 199999
50 Correct 230 ms 16496 KB n = 199991
51 Correct 242 ms 20488 KB n = 199993
52 Correct 167 ms 21168 KB n = 152076
53 Correct 106 ms 21168 KB n = 93249
54 Correct 207 ms 27056 KB n = 199910
55 Correct 202 ms 30676 KB n = 199999
56 Correct 205 ms 32880 KB n = 199997
57 Correct 204 ms 35560 KB n = 171294
58 Correct 159 ms 37032 KB n = 140872
59 Correct 204 ms 41784 KB n = 199886
60 Correct 185 ms 46068 KB n = 199996
61 Correct 189 ms 48672 KB n = 200000
62 Correct 210 ms 54596 KB n = 199998
63 Correct 218 ms 57164 KB n = 200000
64 Correct 227 ms 60480 KB n = 199998
65 Correct 201 ms 64780 KB n = 200000
66 Correct 199 ms 65180 KB n = 190000
67 Correct 244 ms 70596 KB n = 177777
68 Correct 127 ms 70596 KB n = 100000
69 Correct 257 ms 74452 KB n = 200000
70 Correct 256 ms 80648 KB n = 200000
71 Correct 238 ms 84508 KB n = 200000
72 Correct 235 ms 86108 KB n = 200000
73 Correct 247 ms 89976 KB n = 200000
74 Correct 319 ms 93956 KB n = 200000
75 Correct 202 ms 97692 KB n = 200000
76 Correct 205 ms 101612 KB n = 200000
77 Correct 198 ms 103976 KB n = 200000
78 Correct 208 ms 110300 KB n = 200000
79 Correct 208 ms 112092 KB n = 184307
80 Correct 74 ms 112092 KB n = 76040
81 Correct 200 ms 116564 KB n = 199981
82 Correct 199 ms 121004 KB n = 199994
83 Correct 205 ms 123468 KB n = 199996
84 Correct 224 ms 129612 KB n = 199998
85 Correct 228 ms 131944 KB n = 200000
86 Correct 266 ms 135300 KB n = 199998
87 Correct 198 ms 139496 KB n = 200000
88 Correct 221 ms 140996 KB n = 200000
89 Correct 210 ms 147256 KB n = 200000
90 Correct 207 ms 148060 KB n = 200000
91 Correct 255 ms 154248 KB n = 200000
92 Correct 247 ms 158168 KB n = 200000