oj.uz

Submission #1007946

# Submission time Handle Problem Language Result Execution time Memory
1007946 2024-06-26T02:04:41 Z bachhoangxuan Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 187 ms 19116 KB 
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    long long res=0;
    vector<int> com;
    s.push_back(inf);
    t.push_back(0);
    int n=(int)s.size();
    for(int i=0;i<n;i++) com.push_back(s[i]),com.push_back(t[i]);
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    int sz=(int)com.size();
    vector<int> cnt(sz),par(sz);
    iota(par.begin(),par.end(),0);
    function<int(int)> findpar = [&](int u){
        if(u!=par[u]) return par[u]=findpar(par[u]);
        return u;
    };
    auto unions = [&](int u,int v){
        u=findpar(u);v=findpar(v);
        if(u!=v) par[v]=u;
        return (u!=v);
    };
    for(int i=0;i<n;i++){
        int l=lower_bound(com.begin(),com.end(),s[i])-com.begin();
        int r=lower_bound(com.begin(),com.end(),t[i])-com.begin();
        cnt[l]++;cnt[r]--;unions(l,r);
    }
    for(int i=1;i<sz;i++){
        cnt[i]+=cnt[i-1];
        if(cnt[i-1]){
            unions(i-1,i);
            if(cnt[i-1]>0) res+=1LL*cnt[i-1]*(com[i]-com[i-1]);
        }
    }
    vector<pair<int,int>> e;
    for(int i=1;i<sz;i++) e.push_back({com[i]-com[i-1],i});
    sort(e.begin(),e.end());
    for(auto [x,i]:e) if(unions(i-1,i)) res+=x;
    return res;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 18104 KB n = 199999
2 Correct 178 ms 16564 KB n = 199991
3 Correct 168 ms 17472 KB n = 199993
4 Correct 121 ms 14632 KB n = 152076
5 Correct 81 ms 8076 KB n = 93249
6 Correct 140 ms 15796 KB n = 199910
7 Correct 154 ms 15620 KB n = 199999
8 Correct 131 ms 15280 KB n = 199997
9 Correct 141 ms 14740 KB n = 171294
10 Correct 114 ms 14088 KB n = 140872
11 Correct 146 ms 15540 KB n = 199886
12 Correct 157 ms 16612 KB n = 199996
13 Correct 143 ms 16140 KB n = 200000
14 Correct 187 ms 17072 KB n = 199998
15 Correct 156 ms 18612 KB n = 200000
16 Correct 171 ms 19116 KB n = 199998
17 Correct 163 ms 16828 KB n = 200000
18 Correct 152 ms 17708 KB n = 190000
19 Correct 137 ms 15204 KB n = 177777
20 Correct 76 ms 8388 KB n = 100000
21 Correct 178 ms 16932 KB n = 200000
22 Correct 164 ms 17420 KB n = 200000
23 Correct 167 ms 17332 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 2
2 Correct 0 ms 348 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Correct 0 ms 348 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 0 ms 348 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 0 ms 348 KB n = 8
11 Correct 0 ms 348 KB n = 8
12 Correct 1 ms 344 KB n = 8
13 Correct 0 ms 348 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 1 ms 348 KB n = 8
16 Correct 0 ms 348 KB n = 8
17 Correct 0 ms 348 KB n = 8
18 Correct 0 ms 348 KB n = 8
19 Correct 0 ms 348 KB n = 3
20 Correct 0 ms 344 KB n = 7
21 Correct 0 ms 348 KB n = 8
22 Correct 0 ms 348 KB n = 8
23 Correct 0 ms 348 KB n = 8
24 Correct 0 ms 348 KB n = 8
25 Correct 0 ms 344 KB n = 8
26 Correct 0 ms 348 KB n = 8
27 Correct 0 ms 348 KB n = 8
28 Correct 1 ms 348 KB n = 8
29 Correct 0 ms 348 KB n = 16
30 Correct 0 ms 348 KB n = 16
31 Correct 0 ms 348 KB n = 16
32 Correct 1 ms 344 KB n = 16
33 Correct 0 ms 348 KB n = 16
34 Correct 0 ms 348 KB n = 16
35 Correct 0 ms 348 KB n = 16
36 Correct 0 ms 348 KB n = 15
37 Correct 0 ms 344 KB n = 8
38 Correct 0 ms 344 KB n = 16
39 Correct 1 ms 348 KB n = 16
40 Correct 0 ms 348 KB n = 9
41 Correct 1 ms 348 KB n = 16
42 Correct 0 ms 348 KB n = 16
43 Correct 0 ms 600 KB n = 16
44 Correct 1 ms 344 KB n = 9
45 Correct 0 ms 348 KB n = 15
46 Correct 0 ms 348 KB n = 16
47 Correct 0 ms 348 KB n = 16
48 Correct 0 ms 348 KB n = 16
49 Correct 168 ms 18104 KB n = 199999
50 Correct 178 ms 16564 KB n = 199991
51 Correct 168 ms 17472 KB n = 199993
52 Correct 121 ms 14632 KB n = 152076
53 Correct 81 ms 8076 KB n = 93249
54 Correct 140 ms 15796 KB n = 199910
55 Correct 154 ms 15620 KB n = 199999
56 Correct 131 ms 15280 KB n = 199997
57 Correct 141 ms 14740 KB n = 171294
58 Correct 114 ms 14088 KB n = 140872
59 Correct 146 ms 15540 KB n = 199886
60 Correct 157 ms 16612 KB n = 199996
61 Correct 143 ms 16140 KB n = 200000
62 Correct 187 ms 17072 KB n = 199998
63 Correct 156 ms 18612 KB n = 200000
64 Correct 171 ms 19116 KB n = 199998
65 Correct 163 ms 16828 KB n = 200000
66 Correct 152 ms 17708 KB n = 190000
67 Correct 137 ms 15204 KB n = 177777
68 Correct 76 ms 8388 KB n = 100000
69 Correct 178 ms 16932 KB n = 200000
70 Correct 164 ms 17420 KB n = 200000
71 Correct 167 ms 17332 KB n = 200000
72 Correct 172 ms 16684 KB n = 200000
73 Correct 175 ms 16816 KB n = 200000
74 Correct 160 ms 18096 KB n = 200000
75 Correct 160 ms 18356 KB n = 200000
76 Correct 157 ms 16676 KB n = 200000
77 Correct 113 ms 14140 KB n = 200000
78 Correct 117 ms 13616 KB n = 200000
79 Correct 157 ms 15788 KB n = 184307
80 Correct 59 ms 6912 KB n = 76040
81 Correct 144 ms 16056 KB n = 199981
82 Correct 156 ms 17592 KB n = 199994
83 Correct 146 ms 16804 KB n = 199996
84 Correct 161 ms 18096 KB n = 199998
85 Correct 161 ms 16824 KB n = 200000
86 Correct 166 ms 17332 KB n = 199998
87 Correct 157 ms 18100 KB n = 200000
88 Correct 161 ms 18084 KB n = 200000
89 Correct 147 ms 16816 KB n = 200000
90 Correct 170 ms 16816 KB n = 200000
91 Correct 175 ms 16544 KB n = 200000
92 Correct 161 ms 16820 KB n = 200000