oj.uz

답안 #389042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389042 2021-04-13T14:44:22 Z Keshi Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 276 ms 27656 KB 
//In the name of God
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll dsu[maxn], sz[maxn], ps[maxn];

ll par(ll v){
	if(dsu[v] != v) dsu[v] = par(dsu[v]);
	return dsu[v];
}

bool Union(ll v, ll u){
	v = par(v);
	u = par(u);
	if(u == v) return 0;
	if(sz[v] < sz[u]) swap(v, u);
	sz[v] += sz[u];
	dsu[u] = v;
	return 1;
}

long long plan_roller_coaster(vector<int> s, vector<int> t){
	for(ll i = 0; i < maxn; i++){
		dsu[i] = i;
		sz[i] = 1;
	}
	s.pb(inf + 10);
	t.pb(0);
	ll n = Sz(s);
	vector<ll> vec;
	for(ll i = 0; i < n; i++){
		vec.pb(s[i]);
		vec.pb(t[i]);
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for(ll i = 0; i < n; i++){
		s[i] = lower_bound(all(vec), s[i]) - vec.begin();
		t[i] = lower_bound(all(vec), t[i]) - vec.begin();
		Union(s[i], t[i]);
		ps[s[i] + 1]++;
		ps[t[i] + 1]--;
	}
	vector<pll> e;
	ll ans = 0;
	for(ll i = 1; i < Sz(vec); i++){
		ps[i] += ps[i - 1];
		if(ps[i] > 0) ans += ps[i] * (vec[i] - vec[i - 1]);
		if(ps[i] == 0) e.pb(Mp(vec[i] - vec[i - 1], i));
		else Union(i - 1, i);
	}
	sort(all(e));
	for(pll i : e){
		if(Union(i.S, i.S - 1)){
			ans += i.F;
		}
	}
    return ans;
}

/*int main(){
    fast_io;



    return 0;
}*/

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 18488 KB n = 199999
2 Correct 226 ms 22304 KB n = 199991
3 Correct 217 ms 22420 KB n = 199993
4 Correct 160 ms 18880 KB n = 152076
5 Correct 102 ms 14800 KB n = 93249
6 Correct 195 ms 20636 KB n = 199910
7 Correct 192 ms 21532 KB n = 199999
8 Correct 184 ms 20756 KB n = 199997
9 Correct 186 ms 20248 KB n = 171294
10 Correct 153 ms 17500 KB n = 140872
11 Correct 211 ms 20760 KB n = 199886
12 Correct 201 ms 21724 KB n = 199996
13 Correct 193 ms 20888 KB n = 200000
14 Correct 214 ms 26688 KB n = 199998
15 Correct 235 ms 26528 KB n = 200000
16 Correct 226 ms 27036 KB n = 199998
17 Correct 213 ms 22428 KB n = 200000
18 Correct 203 ms 21776 KB n = 190000
19 Correct 181 ms 20908 KB n = 177777
20 Correct 90 ms 15260 KB n = 100000
21 Correct 217 ms 22412 KB n = 200000
22 Correct 251 ms 27656 KB n = 200000
23 Correct 262 ms 27540 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8012 KB n = 2
2 Correct 5 ms 8012 KB n = 2
3 Correct 5 ms 8012 KB n = 2
4 Correct 5 ms 8012 KB n = 2
5 Correct 4 ms 8012 KB n = 2
6 Correct 5 ms 8012 KB n = 2
7 Correct 4 ms 8012 KB n = 3
8 Correct 4 ms 8016 KB n = 3
9 Correct 5 ms 8012 KB n = 3
10 Correct 5 ms 8012 KB n = 8
11 Correct 4 ms 8012 KB n = 8
12 Correct 5 ms 8012 KB n = 8
13 Correct 5 ms 8012 KB n = 8
14 Correct 5 ms 8012 KB n = 8
15 Correct 4 ms 8012 KB n = 8
16 Correct 5 ms 8108 KB n = 8
17 Correct 6 ms 8012 KB n = 8
18 Correct 5 ms 8012 KB n = 8
19 Correct 4 ms 8012 KB n = 3
20 Correct 5 ms 8012 KB n = 7
21 Correct 4 ms 8012 KB n = 8
22 Correct 6 ms 8012 KB n = 8
23 Correct 5 ms 8012 KB n = 8
24 Correct 6 ms 8012 KB n = 8
25 Correct 6 ms 8112 KB n = 8
26 Correct 4 ms 8012 KB n = 8
27 Correct 5 ms 8012 KB n = 8
28 Correct 5 ms 8012 KB n = 8
29 Correct 5 ms 8012 KB n = 16
30 Correct 5 ms 8012 KB n = 16
31 Correct 4 ms 8012 KB n = 16
32 Correct 4 ms 8012 KB n = 16
33 Correct 5 ms 8136 KB n = 16
34 Correct 5 ms 8012 KB n = 16
35 Correct 5 ms 8012 KB n = 16
36 Correct 5 ms 8012 KB n = 15
37 Correct 5 ms 8012 KB n = 8
38 Correct 4 ms 8012 KB n = 16
39 Correct 5 ms 8012 KB n = 16
40 Correct 6 ms 8012 KB n = 9
41 Correct 5 ms 8012 KB n = 16
42 Correct 5 ms 8012 KB n = 16
43 Correct 5 ms 8012 KB n = 16
44 Correct 5 ms 8012 KB n = 9
45 Correct 5 ms 8012 KB n = 15
46 Correct 5 ms 8012 KB n = 16
47 Correct 5 ms 8160 KB n = 16
48 Correct 5 ms 8012 KB n = 16
49 Correct 217 ms 18488 KB n = 199999
50 Correct 226 ms 22304 KB n = 199991
51 Correct 217 ms 22420 KB n = 199993
52 Correct 160 ms 18880 KB n = 152076
53 Correct 102 ms 14800 KB n = 93249
54 Correct 195 ms 20636 KB n = 199910
55 Correct 192 ms 21532 KB n = 199999
56 Correct 184 ms 20756 KB n = 199997
57 Correct 186 ms 20248 KB n = 171294
58 Correct 153 ms 17500 KB n = 140872
59 Correct 211 ms 20760 KB n = 199886
60 Correct 201 ms 21724 KB n = 199996
61 Correct 193 ms 20888 KB n = 200000
62 Correct 214 ms 26688 KB n = 199998
63 Correct 235 ms 26528 KB n = 200000
64 Correct 226 ms 27036 KB n = 199998
65 Correct 213 ms 22428 KB n = 200000
66 Correct 203 ms 21776 KB n = 190000
67 Correct 181 ms 20908 KB n = 177777
68 Correct 90 ms 15260 KB n = 100000
69 Correct 217 ms 22412 KB n = 200000
70 Correct 251 ms 27656 KB n = 200000
71 Correct 262 ms 27540 KB n = 200000
72 Correct 221 ms 22416 KB n = 200000
73 Correct 225 ms 22372 KB n = 200000
74 Correct 217 ms 22412 KB n = 200000
75 Correct 207 ms 22300 KB n = 200000
76 Correct 208 ms 22428 KB n = 200000
77 Correct 163 ms 20748 KB n = 200000
78 Correct 190 ms 25884 KB n = 200000
79 Correct 203 ms 21136 KB n = 184307
80 Correct 71 ms 13420 KB n = 76040
81 Correct 193 ms 20752 KB n = 199981
82 Correct 199 ms 21648 KB n = 199994
83 Correct 190 ms 20964 KB n = 199996
84 Correct 210 ms 26652 KB n = 199998
85 Correct 217 ms 26516 KB n = 200000
86 Correct 219 ms 27036 KB n = 199998
87 Correct 216 ms 22416 KB n = 200000
88 Correct 219 ms 22416 KB n = 200000
89 Correct 206 ms 22416 KB n = 200000
90 Correct 213 ms 22300 KB n = 200000
91 Correct 250 ms 27592 KB n = 200000
92 Correct 276 ms 27532 KB n = 200000