oj.uz

Submission #159037

# Submission time Handle Problem Language Result Execution time Memory
159037 2019-10-20T08:22:25 Z PeppaPig Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 339 ms 16472 KB 
#include "railroad.h"
#include <bits/stdc++.h>

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

const int N = 4e5+5;

int n;
int qs[N], par[N];
vector<int> coord = {0, (int)2e9};

int get(int x) { return lower_bound(coord.begin(), coord.end(), x) - coord.begin() + 1; }

int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

long plan_roller_coaster(vector<int> s, vector<int> t) {
    n = s.size();
    iota(par, par+N, 0);
    for(int i = 0; i < n; i++) {
        coord.emplace_back(s[i]);
        coord.emplace_back(t[i]);
    }
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
    --qs[get(0)], ++qs[get(2e9)];
    for(int i = 0; i < n; i++) {
        int a = get(s[i]), b = get(t[i]);
        if(s[i] < t[i]) ++qs[a], --qs[b];
        else --qs[b], ++qs[a];
        par[find(a)] = find(b);
    }
    for(int i = 1; i <= coord.size(); i++) qs[i] += qs[i-1];

    long ans = 0;
    vector<pii> E;
    for(int i = 1; i < coord.size(); i++) {
        long d = coord[i] - coord[i-1];
        if(qs[i] > 0) ans += qs[i] * d;
        if(qs[i] != 0) par[find(i)] = find(i + 1);
        else E.emplace_back(d, i);
    }
    sort(E.begin(), E.end());
    for(pii e : E) {
        long d, i; tie(d, i) = e;
        if(find(i) != find(i + 1)) {
            par[find(i)] = find(i + 1);
            ans += d;
        }
    }
    return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= coord.size(); i++) qs[i] += qs[i-1];
                    ~~^~~~~~~~~~~~~~~
railroad.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < coord.size(); i++) {
                    ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 12136 KB n = 199999
2 Correct 231 ms 12136 KB n = 199991
3 Correct 226 ms 12264 KB n = 199993
4 Correct 166 ms 9448 KB n = 152076
5 Correct 101 ms 6748 KB n = 93249
6 Correct 187 ms 10728 KB n = 199910
7 Correct 191 ms 11368 KB n = 199999
8 Correct 183 ms 10856 KB n = 199997
9 Correct 192 ms 10604 KB n = 171294
10 Correct 158 ms 9196 KB n = 140872
11 Correct 188 ms 10860 KB n = 199886
12 Correct 203 ms 12904 KB n = 199996
13 Correct 190 ms 12316 KB n = 200000
14 Correct 215 ms 15380 KB n = 199998
15 Correct 219 ms 15332 KB n = 200000
16 Correct 233 ms 15844 KB n = 199998
17 Correct 212 ms 15336 KB n = 200000
18 Correct 199 ms 11880 KB n = 190000
19 Correct 180 ms 13924 KB n = 177777
20 Correct 101 ms 7204 KB n = 100000
21 Correct 213 ms 12184 KB n = 200000
22 Correct 260 ms 16356 KB n = 200000
23 Correct 262 ms 16472 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB n = 2
2 Correct 3 ms 1912 KB n = 2
3 Correct 3 ms 1912 KB n = 2
4 Correct 4 ms 1912 KB n = 2
5 Correct 4 ms 1912 KB n = 2
6 Correct 3 ms 1832 KB n = 2
7 Correct 3 ms 1912 KB n = 3
8 Correct 3 ms 1912 KB n = 3
9 Correct 3 ms 1916 KB n = 3
10 Correct 3 ms 1912 KB n = 8
11 Correct 3 ms 1884 KB n = 8
12 Correct 3 ms 1912 KB n = 8
13 Correct 3 ms 1912 KB n = 8
14 Correct 3 ms 1912 KB n = 8
15 Correct 3 ms 1916 KB n = 8
16 Correct 3 ms 1912 KB n = 8
17 Correct 3 ms 1916 KB n = 8
18 Correct 3 ms 1912 KB n = 8
19 Correct 3 ms 1912 KB n = 3
20 Correct 3 ms 1912 KB n = 7
21 Correct 3 ms 1912 KB n = 8
22 Correct 3 ms 1912 KB n = 8
23 Correct 3 ms 1912 KB n = 8
24 Correct 3 ms 1912 KB n = 8
25 Correct 3 ms 1912 KB n = 8
26 Correct 3 ms 1912 KB n = 8
27 Correct 3 ms 1912 KB n = 8
28 Correct 3 ms 1912 KB n = 8
29 Correct 3 ms 1916 KB n = 16
30 Correct 3 ms 1912 KB n = 16
31 Correct 3 ms 1912 KB n = 16
32 Correct 3 ms 1916 KB n = 16
33 Correct 3 ms 1912 KB n = 16
34 Correct 3 ms 1912 KB n = 16
35 Correct 3 ms 1916 KB n = 16
36 Correct 3 ms 1912 KB n = 15
37 Correct 3 ms 1912 KB n = 8
38 Correct 3 ms 1912 KB n = 16
39 Correct 3 ms 1916 KB n = 16
40 Correct 3 ms 1912 KB n = 9
41 Correct 3 ms 1912 KB n = 16
42 Correct 3 ms 1912 KB n = 16
43 Correct 3 ms 1912 KB n = 16
44 Correct 3 ms 1912 KB n = 9
45 Correct 4 ms 1912 KB n = 15
46 Correct 3 ms 1912 KB n = 16
47 Correct 3 ms 1912 KB n = 16
48 Correct 3 ms 1912 KB n = 16
49 Correct 224 ms 12136 KB n = 199999
50 Correct 231 ms 12136 KB n = 199991
51 Correct 226 ms 12264 KB n = 199993
52 Correct 166 ms 9448 KB n = 152076
53 Correct 101 ms 6748 KB n = 93249
54 Correct 187 ms 10728 KB n = 199910
55 Correct 191 ms 11368 KB n = 199999
56 Correct 183 ms 10856 KB n = 199997
57 Correct 192 ms 10604 KB n = 171294
58 Correct 158 ms 9196 KB n = 140872
59 Correct 188 ms 10860 KB n = 199886
60 Correct 203 ms 12904 KB n = 199996
61 Correct 190 ms 12316 KB n = 200000
62 Correct 215 ms 15380 KB n = 199998
63 Correct 219 ms 15332 KB n = 200000
64 Correct 233 ms 15844 KB n = 199998
65 Correct 212 ms 15336 KB n = 200000
66 Correct 199 ms 11880 KB n = 190000
67 Correct 180 ms 13924 KB n = 177777
68 Correct 101 ms 7204 KB n = 100000
69 Correct 213 ms 12184 KB n = 200000
70 Correct 260 ms 16356 KB n = 200000
71 Correct 262 ms 16472 KB n = 200000
72 Correct 227 ms 12252 KB n = 200000
73 Correct 233 ms 12308 KB n = 200000
74 Correct 226 ms 12264 KB n = 200000
75 Correct 205 ms 12136 KB n = 200000
76 Correct 204 ms 12184 KB n = 200000
77 Correct 192 ms 11496 KB n = 200000
78 Correct 213 ms 15460 KB n = 200000
79 Correct 215 ms 11160 KB n = 184307
80 Correct 84 ms 5968 KB n = 76040
81 Correct 188 ms 10864 KB n = 199981
82 Correct 195 ms 12776 KB n = 199994
83 Correct 186 ms 12184 KB n = 199996
84 Correct 213 ms 15516 KB n = 199998
85 Correct 218 ms 15460 KB n = 200000
86 Correct 245 ms 15716 KB n = 199998
87 Correct 207 ms 15336 KB n = 200000
88 Correct 216 ms 12940 KB n = 200000
89 Correct 222 ms 15340 KB n = 200000
90 Correct 221 ms 12208 KB n = 200000
91 Correct 263 ms 16292 KB n = 200000
92 Correct 339 ms 16244 KB n = 200000