oj.uz

Submission #45217

# Submission time Handle Problem Language Result Execution time Memory
45217 2018-04-11T21:42:47 Z reality Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 340 ms 159080 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#include "railroad.h"
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int oo = 1e9 + 5;
const int N = (int)(1e6) + 5;
int sum[N];
int f[N];
int get(int k)
{
    return k == f[k] ? k : f[k] = get(f[k]);
}
ll plan_roller_coaster(vi l,vi r)
{
    l.pb(oo);
    r.pb(1);
    int n = l.size();
    vi ss;
    for (int i = 0;i < n;++i)
        ss.pb(l[i]),ss.pb(r[i]);
    sort(all(ss));
    ss.resize(unique(all(ss)) - ss.begin());
    const int sz = ss.size();
    for (int i = 1;i <= sz;++i)
        f[i] = i;
    for (int i = 0;i < n;++i)
    {
        int l1 = lower_bound(all(ss),l[i]) - ss.begin() + 1;
        int r1 = lower_bound(all(ss),r[i]) - ss.begin() + 1;
        sum[l1] += 1;
        sum[r1] -= 1;
        f[get(l1)] = get(r1);
    }
    ll ans = 0;
    for (int i = 1;i <= sz;++i)
        sum[i] += sum[i - 1];
    for (int i = 1;i <= sz;++i)
        if (sum[i])
            ans += 1ll * max(0,sum[i]) * (ss[i] - ss[i - 1]),f[get(i)] = get(i + 1);
    vi p;
    for (int i = 0;i + 1 < sz;++i)
        p.pb(i);
    sort(all(p),[&](int x,int y)
         {
            return ss[x + 1] - ss[x] < ss[y + 1] - ss[y];
         });
    for (auto index : p)
        if (get(index + 1) != get(index + 2))
            ans += ss[index + 1] - ss[index],f[get(index + 1)] = get(index + 2);
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB n = 2
2 Correct 2 ms 592 KB n = 2
3 Correct 2 ms 712 KB n = 2
4 Correct 2 ms 712 KB n = 2
5 Correct 2 ms 712 KB n = 2
6 Correct 2 ms 740 KB n = 2
7 Correct 2 ms 764 KB n = 3
8 Correct 2 ms 764 KB n = 3
9 Correct 2 ms 812 KB n = 3
10 Correct 2 ms 816 KB n = 8
11 Correct 2 ms 820 KB n = 8
12 Correct 2 ms 824 KB n = 8
13 Correct 2 ms 828 KB n = 8
14 Correct 2 ms 832 KB n = 8
15 Correct 2 ms 836 KB n = 8
16 Correct 2 ms 840 KB n = 8
17 Correct 2 ms 844 KB n = 8
18 Correct 2 ms 848 KB n = 8
19 Correct 2 ms 852 KB n = 3
20 Correct 2 ms 856 KB n = 7
21 Correct 2 ms 864 KB n = 8
22 Correct 2 ms 864 KB n = 8
23 Correct 2 ms 908 KB n = 8
24 Correct 2 ms 916 KB n = 8
25 Correct 2 ms 916 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB n = 2
2 Correct 2 ms 592 KB n = 2
3 Correct 2 ms 712 KB n = 2
4 Correct 2 ms 712 KB n = 2
5 Correct 2 ms 712 KB n = 2
6 Correct 2 ms 740 KB n = 2
7 Correct 2 ms 764 KB n = 3
8 Correct 2 ms 764 KB n = 3
9 Correct 2 ms 812 KB n = 3
10 Correct 2 ms 816 KB n = 8
11 Correct 2 ms 820 KB n = 8
12 Correct 2 ms 824 KB n = 8
13 Correct 2 ms 828 KB n = 8
14 Correct 2 ms 832 KB n = 8
15 Correct 2 ms 836 KB n = 8
16 Correct 2 ms 840 KB n = 8
17 Correct 2 ms 844 KB n = 8
18 Correct 2 ms 848 KB n = 8
19 Correct 2 ms 852 KB n = 3
20 Correct 2 ms 856 KB n = 7
21 Correct 2 ms 864 KB n = 8
22 Correct 2 ms 864 KB n = 8
23 Correct 2 ms 908 KB n = 8
24 Correct 2 ms 916 KB n = 8
25 Correct 2 ms 916 KB n = 8
26 Correct 2 ms 920 KB n = 8
27 Correct 2 ms 940 KB n = 8
28 Correct 2 ms 948 KB n = 8
29 Correct 2 ms 952 KB n = 16
30 Correct 2 ms 956 KB n = 16
31 Correct 2 ms 960 KB n = 16
32 Correct 2 ms 964 KB n = 16
33 Correct 2 ms 968 KB n = 16
34 Correct 2 ms 968 KB n = 16
35 Correct 2 ms 968 KB n = 16
36 Correct 2 ms 968 KB n = 15
37 Correct 2 ms 984 KB n = 8
38 Correct 2 ms 988 KB n = 16
39 Correct 2 ms 992 KB n = 16
40 Correct 2 ms 996 KB n = 9
41 Correct 2 ms 1000 KB n = 16
42 Correct 2 ms 1004 KB n = 16
43 Correct 2 ms 1008 KB n = 16
44 Correct 2 ms 1016 KB n = 9
45 Correct 2 ms 1016 KB n = 15
46 Correct 2 ms 1016 KB n = 16
47 Correct 2 ms 1020 KB n = 16
48 Correct 2 ms 1028 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 15844 KB n = 199999
2 Correct 291 ms 19724 KB n = 199991
3 Correct 298 ms 23604 KB n = 199993
4 Correct 208 ms 24404 KB n = 152076
5 Correct 127 ms 24404 KB n = 93249
6 Correct 221 ms 30204 KB n = 199910
7 Correct 232 ms 34224 KB n = 199999
8 Correct 207 ms 36496 KB n = 199997
9 Correct 242 ms 38780 KB n = 171294
10 Correct 198 ms 40208 KB n = 140872
11 Correct 216 ms 44924 KB n = 199886
12 Correct 237 ms 49084 KB n = 199996
13 Correct 213 ms 51548 KB n = 200000
14 Correct 236 ms 56436 KB n = 199998
15 Correct 234 ms 58652 KB n = 200000
16 Correct 261 ms 61880 KB n = 199998
17 Correct 265 ms 67876 KB n = 200000
18 Correct 263 ms 68252 KB n = 190000
19 Correct 240 ms 73828 KB n = 177777
20 Correct 141 ms 73828 KB n = 100000
21 Correct 301 ms 77756 KB n = 200000
22 Correct 280 ms 81516 KB n = 200000
23 Correct 253 ms 85420 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB n = 2
2 Correct 2 ms 592 KB n = 2
3 Correct 2 ms 712 KB n = 2
4 Correct 2 ms 712 KB n = 2
5 Correct 2 ms 712 KB n = 2
6 Correct 2 ms 740 KB n = 2
7 Correct 2 ms 764 KB n = 3
8 Correct 2 ms 764 KB n = 3
9 Correct 2 ms 812 KB n = 3
10 Correct 2 ms 816 KB n = 8
11 Correct 2 ms 820 KB n = 8
12 Correct 2 ms 824 KB n = 8
13 Correct 2 ms 828 KB n = 8
14 Correct 2 ms 832 KB n = 8
15 Correct 2 ms 836 KB n = 8
16 Correct 2 ms 840 KB n = 8
17 Correct 2 ms 844 KB n = 8
18 Correct 2 ms 848 KB n = 8
19 Correct 2 ms 852 KB n = 3
20 Correct 2 ms 856 KB n = 7
21 Correct 2 ms 864 KB n = 8
22 Correct 2 ms 864 KB n = 8
23 Correct 2 ms 908 KB n = 8
24 Correct 2 ms 916 KB n = 8
25 Correct 2 ms 916 KB n = 8
26 Correct 2 ms 920 KB n = 8
27 Correct 2 ms 940 KB n = 8
28 Correct 2 ms 948 KB n = 8
29 Correct 2 ms 952 KB n = 16
30 Correct 2 ms 956 KB n = 16
31 Correct 2 ms 960 KB n = 16
32 Correct 2 ms 964 KB n = 16
33 Correct 2 ms 968 KB n = 16
34 Correct 2 ms 968 KB n = 16
35 Correct 2 ms 968 KB n = 16
36 Correct 2 ms 968 KB n = 15
37 Correct 2 ms 984 KB n = 8
38 Correct 2 ms 988 KB n = 16
39 Correct 2 ms 992 KB n = 16
40 Correct 2 ms 996 KB n = 9
41 Correct 2 ms 1000 KB n = 16
42 Correct 2 ms 1004 KB n = 16
43 Correct 2 ms 1008 KB n = 16
44 Correct 2 ms 1016 KB n = 9
45 Correct 2 ms 1016 KB n = 15
46 Correct 2 ms 1016 KB n = 16
47 Correct 2 ms 1020 KB n = 16
48 Correct 2 ms 1028 KB n = 16
49 Correct 279 ms 15844 KB n = 199999
50 Correct 291 ms 19724 KB n = 199991
51 Correct 298 ms 23604 KB n = 199993
52 Correct 208 ms 24404 KB n = 152076
53 Correct 127 ms 24404 KB n = 93249
54 Correct 221 ms 30204 KB n = 199910
55 Correct 232 ms 34224 KB n = 199999
56 Correct 207 ms 36496 KB n = 199997
57 Correct 242 ms 38780 KB n = 171294
58 Correct 198 ms 40208 KB n = 140872
59 Correct 216 ms 44924 KB n = 199886
60 Correct 237 ms 49084 KB n = 199996
61 Correct 213 ms 51548 KB n = 200000
62 Correct 236 ms 56436 KB n = 199998
63 Correct 234 ms 58652 KB n = 200000
64 Correct 261 ms 61880 KB n = 199998
65 Correct 265 ms 67876 KB n = 200000
66 Correct 263 ms 68252 KB n = 190000
67 Correct 240 ms 73828 KB n = 177777
68 Correct 141 ms 73828 KB n = 100000
69 Correct 301 ms 77756 KB n = 200000
70 Correct 280 ms 81516 KB n = 200000
71 Correct 253 ms 85420 KB n = 200000
72 Correct 299 ms 89440 KB n = 200000
73 Correct 299 ms 93228 KB n = 200000
74 Correct 338 ms 97108 KB n = 200000
75 Correct 264 ms 100988 KB n = 200000
76 Correct 304 ms 104936 KB n = 200000
77 Correct 219 ms 109004 KB n = 200000
78 Correct 233 ms 109708 KB n = 200000
79 Correct 340 ms 115468 KB n = 184307
80 Correct 124 ms 115468 KB n = 76040
81 Correct 295 ms 119768 KB n = 199981
82 Correct 286 ms 123916 KB n = 199994
83 Correct 222 ms 126356 KB n = 199996
84 Correct 257 ms 131068 KB n = 199998
85 Correct 236 ms 133508 KB n = 200000
86 Correct 269 ms 136960 KB n = 199998
87 Correct 330 ms 142724 KB n = 200000
88 Correct 314 ms 144196 KB n = 200000
89 Correct 263 ms 150512 KB n = 200000
90 Correct 276 ms 151464 KB n = 200000
91 Correct 261 ms 155216 KB n = 200000
92 Correct 260 ms 159080 KB n = 200000