oj.uz

답안 #794278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794278 2023-07-26T11:59:58 Z becaido Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 178 ms 18756 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "railroad.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 1e9;
const int SIZE = 4e5 + 5;

int n, m;
ll ans;
int d[SIZE];
vector<int> lis;
int to[SIZE], h[SIZE];

int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool mer(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return 0;
    if (h[a] < h[b]) swap(a, b);
    to[b] = a;
    h[a] += (h[a] == h[b]);
    return 1;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    n = s.size();
    lis.clear();
    lis.pb(1), lis.pb(INF);
    lis.insert(lis.end(), s.begin(), s.end());
    lis.insert(lis.end(), t.begin(), t.end());
    sort(lis.begin(), lis.end());
    lis.erase(unique(lis.begin(), lis.end()), lis.end());
    m = lis.size();
    iota(to, to + m, 0);
    fill(h, h + m, 0);
    fill(d, d + m, 0);
    ans = 0;
    mer(0, m - 1);
    d[m - 1]++, d[0]--;
    FOR (i, 0, n - 1) {
        int l = lower_bound(lis.begin(), lis.end(), s[i]) - lis.begin();
        int r = lower_bound(lis.begin(), lis.end(), t[i]) - lis.begin();
        d[l]++, d[r]--;
        mer(l, r);
    }
    vector<pair<int, int>> e;
    FOR (i, 0, m - 2) {
        if (d[i] != 0) {
            mer(i, i + 1);
            if (d[i] > 0) ans += 1ll * d[i] * (lis[i + 1] - lis[i]);
        }
        e.pb(lis[i + 1] - lis[i], i);
        d[i + 1] += d[i];
    }
    sort(e.begin(), e.end());
    for (auto [w, i] : e) if (mer(i, i + 1)) ans += w;
    return ans;
}

/*
in1
4
1 7
4 3
5 8
6 6
out1
3
*/

#ifdef WAIMAI
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}
#endif

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 316 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 340 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 316 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 340 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 312 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 320 KB n = 16
32 Correct 0 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 312 KB n = 8
38 Correct 0 ms 316 KB n = 16
39 Correct 1 ms 280 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 1 ms 316 KB n = 16
44 Correct 0 ms 312 KB n = 9
45 Correct 0 ms 304 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 14752 KB n = 199999
2 Correct 178 ms 18676 KB n = 199991
3 Correct 157 ms 18612 KB n = 199993
4 Correct 117 ms 15100 KB n = 152076
5 Correct 71 ms 8988 KB n = 93249
6 Correct 139 ms 16696 KB n = 199910
7 Correct 162 ms 17856 KB n = 199999
8 Correct 138 ms 16776 KB n = 199997
9 Correct 141 ms 16712 KB n = 171294
10 Correct 111 ms 13876 KB n = 140872
11 Correct 145 ms 16696 KB n = 199886
12 Correct 149 ms 17984 KB n = 199996
13 Correct 151 ms 16944 KB n = 200000
14 Correct 150 ms 17796 KB n = 199998
15 Correct 151 ms 17672 KB n = 200000
16 Correct 153 ms 18104 KB n = 199998
17 Correct 158 ms 18600 KB n = 200000
18 Correct 156 ms 17968 KB n = 190000
19 Correct 138 ms 17168 KB n = 177777
20 Correct 80 ms 9504 KB n = 100000
21 Correct 155 ms 18604 KB n = 200000
22 Correct 155 ms 18620 KB n = 200000
23 Correct 165 ms 18624 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 316 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 1 ms 340 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 312 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 320 KB n = 16
32 Correct 0 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 312 KB n = 8
38 Correct 0 ms 316 KB n = 16
39 Correct 1 ms 280 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 1 ms 316 KB n = 16
44 Correct 0 ms 312 KB n = 9
45 Correct 0 ms 304 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 162 ms 14752 KB n = 199999
50 Correct 178 ms 18676 KB n = 199991
51 Correct 157 ms 18612 KB n = 199993
52 Correct 117 ms 15100 KB n = 152076
53 Correct 71 ms 8988 KB n = 93249
54 Correct 139 ms 16696 KB n = 199910
55 Correct 162 ms 17856 KB n = 199999
56 Correct 138 ms 16776 KB n = 199997
57 Correct 141 ms 16712 KB n = 171294
58 Correct 111 ms 13876 KB n = 140872
59 Correct 145 ms 16696 KB n = 199886
60 Correct 149 ms 17984 KB n = 199996
61 Correct 151 ms 16944 KB n = 200000
62 Correct 150 ms 17796 KB n = 199998
63 Correct 151 ms 17672 KB n = 200000
64 Correct 153 ms 18104 KB n = 199998
65 Correct 158 ms 18600 KB n = 200000
66 Correct 156 ms 17968 KB n = 190000
67 Correct 138 ms 17168 KB n = 177777
68 Correct 80 ms 9504 KB n = 100000
69 Correct 155 ms 18604 KB n = 200000
70 Correct 155 ms 18620 KB n = 200000
71 Correct 165 ms 18624 KB n = 200000
72 Correct 168 ms 18740 KB n = 200000
73 Correct 162 ms 18612 KB n = 200000
74 Correct 157 ms 18756 KB n = 200000
75 Correct 156 ms 18632 KB n = 200000
76 Correct 156 ms 18720 KB n = 200000
77 Correct 126 ms 14312 KB n = 200000
78 Correct 136 ms 14312 KB n = 200000
79 Correct 149 ms 17404 KB n = 184307
80 Correct 57 ms 7456 KB n = 76040
81 Correct 143 ms 16740 KB n = 199981
82 Correct 153 ms 17976 KB n = 199994
83 Correct 142 ms 16948 KB n = 199996
84 Correct 151 ms 17720 KB n = 199998
85 Correct 150 ms 17684 KB n = 200000
86 Correct 162 ms 18208 KB n = 199998
87 Correct 163 ms 18612 KB n = 200000
88 Correct 165 ms 18688 KB n = 200000
89 Correct 159 ms 18684 KB n = 200000
90 Correct 166 ms 18624 KB n = 200000
91 Correct 163 ms 18704 KB n = 200000
92 Correct 154 ms 18692 KB n = 200000