#include"railroad.h"
#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define V vector
#define Int long long
#define rep(i,a,b) for(Int i=(Int)(a); i<(Int)(b); i++)
#define all(x) (x).begin(), (x).end()
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
const Int INF = 1e18+5;
const Int N = 2e5+5;
Int n;
V<Int> s, t;
map<Int,Int> zip;
V<Int> unzip;
Int ans = 0;
#define mid ((tl+tr)/2)
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
Int st[4*N];
void upd(Int l,Int r,Int x,Int v=0,Int tl=0,Int tr=2*N){
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
st[v] += x; return;
}
upd(l,r,x, lc,tl,mid);
upd(l,r,x, rc,mid+1,tr);
}
Int qry(Int i,Int v=0,Int tl=0,Int tr=2*N){
if(tl==tr) return st[v];
if(i<=mid) return st[v] + qry(i, lc,tl,mid);
else return st[v] + qry(i, rc,mid+1,tr);
}
} segtree;
struct Dsu{
Int p[2*N];
Dsu(){
rep(i,0,2*N) p[i] = i;
}
Int find(Int x){
if(p[x]==x) return x;
return p[x] = find(p[x]);
}
bool same(Int x,Int y){
return find(x)==find(y);
}
void unite(Int x,Int y){
if((x=find(x))==(y=find(y))) return;
p[x] = y;
}
} dsu;
Int plan_roller_coaster(V<int>_s,V<int>_t){
s = V<Int>(all(_s)); t = V<Int>(all(_t));
s.push_back(INF); t.push_back(0);
n = s.size();
rep(i,0,n){
// dbg(s[i]); dbg(t[i]);
zip[s[i]]; zip[t[i]];
}
Int timer = 0;
unzip = V<Int>(zip.size());
for(auto&[x,y] : zip) unzip[y=timer++] = x;
rep(i,0,n){
s[i] = zip[s[i]];
t[i] = zip[t[i]];
// cout << s[i] << " " << t[i] << nl;
if(s[i] < t[i]){
segtree.upd(s[i],t[i]-1, 1);
}
if(t[i] < s[i]){
segtree.upd(t[i],s[i]-1, -1);
}
dsu.unite(s[i], t[i]);
}
// {-w, u, v}
priority_queue<array<Int,3>> pq;
rep(i,0,zip.size()-1){
pq.push({-(unzip[i+1]-unzip[i]), i+1,i});;
Int cnt = segtree.qry(i);
// make edge
if(cnt != 0){
dsu.unite(i+1, i);
}
// make leftward edges
if(cnt > 0){
// dbg(cnt);
// dbg((unzip[i+1]-unzip[i])*cnt);
ans += (unzip[i+1]-unzip[i])*cnt;
}
}
while(!pq.empty()){
auto[w,u,v] = pq.top(); pq.pop();
if(dsu.same(u,v)) continue;
w *= -1;
// assert(0);
ans += w;
dsu.unite(u,v);
}
// dbg(ans);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3412 KB |
n = 2 |
2 |
Correct |
2 ms |
3412 KB |
n = 2 |
3 |
Correct |
1 ms |
3412 KB |
n = 2 |
4 |
Correct |
2 ms |
3412 KB |
n = 2 |
5 |
Correct |
2 ms |
3412 KB |
n = 2 |
6 |
Correct |
2 ms |
3412 KB |
n = 2 |
7 |
Correct |
2 ms |
3412 KB |
n = 3 |
8 |
Correct |
2 ms |
3412 KB |
n = 3 |
9 |
Correct |
1 ms |
3412 KB |
n = 3 |
10 |
Correct |
2 ms |
3412 KB |
n = 8 |
11 |
Correct |
2 ms |
3412 KB |
n = 8 |
12 |
Correct |
2 ms |
3412 KB |
n = 8 |
13 |
Correct |
2 ms |
3412 KB |
n = 8 |
14 |
Correct |
2 ms |
3412 KB |
n = 8 |
15 |
Correct |
2 ms |
3412 KB |
n = 8 |
16 |
Correct |
3 ms |
3412 KB |
n = 8 |
17 |
Correct |
2 ms |
3412 KB |
n = 8 |
18 |
Correct |
3 ms |
3412 KB |
n = 8 |
19 |
Correct |
2 ms |
3412 KB |
n = 3 |
20 |
Correct |
2 ms |
3412 KB |
n = 7 |
21 |
Correct |
2 ms |
3412 KB |
n = 8 |
22 |
Correct |
2 ms |
3412 KB |
n = 8 |
23 |
Correct |
2 ms |
3412 KB |
n = 8 |
24 |
Correct |
2 ms |
3412 KB |
n = 8 |
25 |
Correct |
3 ms |
3412 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3412 KB |
n = 2 |
2 |
Correct |
2 ms |
3412 KB |
n = 2 |
3 |
Correct |
1 ms |
3412 KB |
n = 2 |
4 |
Correct |
2 ms |
3412 KB |
n = 2 |
5 |
Correct |
2 ms |
3412 KB |
n = 2 |
6 |
Correct |
2 ms |
3412 KB |
n = 2 |
7 |
Correct |
2 ms |
3412 KB |
n = 3 |
8 |
Correct |
2 ms |
3412 KB |
n = 3 |
9 |
Correct |
1 ms |
3412 KB |
n = 3 |
10 |
Correct |
2 ms |
3412 KB |
n = 8 |
11 |
Correct |
2 ms |
3412 KB |
n = 8 |
12 |
Correct |
2 ms |
3412 KB |
n = 8 |
13 |
Correct |
2 ms |
3412 KB |
n = 8 |
14 |
Correct |
2 ms |
3412 KB |
n = 8 |
15 |
Correct |
2 ms |
3412 KB |
n = 8 |
16 |
Correct |
3 ms |
3412 KB |
n = 8 |
17 |
Correct |
2 ms |
3412 KB |
n = 8 |
18 |
Correct |
3 ms |
3412 KB |
n = 8 |
19 |
Correct |
2 ms |
3412 KB |
n = 3 |
20 |
Correct |
2 ms |
3412 KB |
n = 7 |
21 |
Correct |
2 ms |
3412 KB |
n = 8 |
22 |
Correct |
2 ms |
3412 KB |
n = 8 |
23 |
Correct |
2 ms |
3412 KB |
n = 8 |
24 |
Correct |
2 ms |
3412 KB |
n = 8 |
25 |
Correct |
3 ms |
3412 KB |
n = 8 |
26 |
Correct |
2 ms |
3412 KB |
n = 8 |
27 |
Correct |
2 ms |
3412 KB |
n = 8 |
28 |
Correct |
2 ms |
3412 KB |
n = 8 |
29 |
Correct |
2 ms |
3412 KB |
n = 16 |
30 |
Correct |
3 ms |
3412 KB |
n = 16 |
31 |
Correct |
2 ms |
3412 KB |
n = 16 |
32 |
Correct |
2 ms |
3412 KB |
n = 16 |
33 |
Correct |
2 ms |
3412 KB |
n = 16 |
34 |
Correct |
2 ms |
3412 KB |
n = 16 |
35 |
Correct |
2 ms |
3412 KB |
n = 16 |
36 |
Correct |
2 ms |
3412 KB |
n = 15 |
37 |
Correct |
2 ms |
3412 KB |
n = 8 |
38 |
Correct |
2 ms |
3412 KB |
n = 16 |
39 |
Correct |
2 ms |
3412 KB |
n = 16 |
40 |
Correct |
2 ms |
3412 KB |
n = 9 |
41 |
Correct |
2 ms |
3412 KB |
n = 16 |
42 |
Correct |
2 ms |
3412 KB |
n = 16 |
43 |
Correct |
2 ms |
3412 KB |
n = 16 |
44 |
Correct |
2 ms |
3412 KB |
n = 9 |
45 |
Correct |
2 ms |
3412 KB |
n = 15 |
46 |
Correct |
2 ms |
3412 KB |
n = 16 |
47 |
Correct |
2 ms |
3412 KB |
n = 16 |
48 |
Correct |
2 ms |
3412 KB |
n = 16 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
882 ms |
56568 KB |
n = 199999 |
2 |
Correct |
851 ms |
56556 KB |
n = 199991 |
3 |
Correct |
813 ms |
56584 KB |
n = 199993 |
4 |
Correct |
609 ms |
48228 KB |
n = 152076 |
5 |
Correct |
355 ms |
29312 KB |
n = 93249 |
6 |
Correct |
708 ms |
50292 KB |
n = 199910 |
7 |
Correct |
648 ms |
55820 KB |
n = 199999 |
8 |
Correct |
630 ms |
50492 KB |
n = 199997 |
9 |
Correct |
674 ms |
52100 KB |
n = 171294 |
10 |
Correct |
544 ms |
45932 KB |
n = 140872 |
11 |
Correct |
673 ms |
50700 KB |
n = 199886 |
12 |
Correct |
640 ms |
55968 KB |
n = 199996 |
13 |
Correct |
593 ms |
51864 KB |
n = 200000 |
14 |
Correct |
588 ms |
55800 KB |
n = 199998 |
15 |
Correct |
657 ms |
55292 KB |
n = 200000 |
16 |
Correct |
696 ms |
56408 KB |
n = 199998 |
17 |
Correct |
733 ms |
56588 KB |
n = 200000 |
18 |
Correct |
737 ms |
55928 KB |
n = 190000 |
19 |
Correct |
626 ms |
53440 KB |
n = 177777 |
20 |
Correct |
303 ms |
30060 KB |
n = 100000 |
21 |
Correct |
820 ms |
56536 KB |
n = 200000 |
22 |
Correct |
760 ms |
56596 KB |
n = 200000 |
23 |
Correct |
821 ms |
56572 KB |
n = 200000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3412 KB |
n = 2 |
2 |
Correct |
2 ms |
3412 KB |
n = 2 |
3 |
Correct |
1 ms |
3412 KB |
n = 2 |
4 |
Correct |
2 ms |
3412 KB |
n = 2 |
5 |
Correct |
2 ms |
3412 KB |
n = 2 |
6 |
Correct |
2 ms |
3412 KB |
n = 2 |
7 |
Correct |
2 ms |
3412 KB |
n = 3 |
8 |
Correct |
2 ms |
3412 KB |
n = 3 |
9 |
Correct |
1 ms |
3412 KB |
n = 3 |
10 |
Correct |
2 ms |
3412 KB |
n = 8 |
11 |
Correct |
2 ms |
3412 KB |
n = 8 |
12 |
Correct |
2 ms |
3412 KB |
n = 8 |
13 |
Correct |
2 ms |
3412 KB |
n = 8 |
14 |
Correct |
2 ms |
3412 KB |
n = 8 |
15 |
Correct |
2 ms |
3412 KB |
n = 8 |
16 |
Correct |
3 ms |
3412 KB |
n = 8 |
17 |
Correct |
2 ms |
3412 KB |
n = 8 |
18 |
Correct |
3 ms |
3412 KB |
n = 8 |
19 |
Correct |
2 ms |
3412 KB |
n = 3 |
20 |
Correct |
2 ms |
3412 KB |
n = 7 |
21 |
Correct |
2 ms |
3412 KB |
n = 8 |
22 |
Correct |
2 ms |
3412 KB |
n = 8 |
23 |
Correct |
2 ms |
3412 KB |
n = 8 |
24 |
Correct |
2 ms |
3412 KB |
n = 8 |
25 |
Correct |
3 ms |
3412 KB |
n = 8 |
26 |
Correct |
2 ms |
3412 KB |
n = 8 |
27 |
Correct |
2 ms |
3412 KB |
n = 8 |
28 |
Correct |
2 ms |
3412 KB |
n = 8 |
29 |
Correct |
2 ms |
3412 KB |
n = 16 |
30 |
Correct |
3 ms |
3412 KB |
n = 16 |
31 |
Correct |
2 ms |
3412 KB |
n = 16 |
32 |
Correct |
2 ms |
3412 KB |
n = 16 |
33 |
Correct |
2 ms |
3412 KB |
n = 16 |
34 |
Correct |
2 ms |
3412 KB |
n = 16 |
35 |
Correct |
2 ms |
3412 KB |
n = 16 |
36 |
Correct |
2 ms |
3412 KB |
n = 15 |
37 |
Correct |
2 ms |
3412 KB |
n = 8 |
38 |
Correct |
2 ms |
3412 KB |
n = 16 |
39 |
Correct |
2 ms |
3412 KB |
n = 16 |
40 |
Correct |
2 ms |
3412 KB |
n = 9 |
41 |
Correct |
2 ms |
3412 KB |
n = 16 |
42 |
Correct |
2 ms |
3412 KB |
n = 16 |
43 |
Correct |
2 ms |
3412 KB |
n = 16 |
44 |
Correct |
2 ms |
3412 KB |
n = 9 |
45 |
Correct |
2 ms |
3412 KB |
n = 15 |
46 |
Correct |
2 ms |
3412 KB |
n = 16 |
47 |
Correct |
2 ms |
3412 KB |
n = 16 |
48 |
Correct |
2 ms |
3412 KB |
n = 16 |
49 |
Correct |
882 ms |
56568 KB |
n = 199999 |
50 |
Correct |
851 ms |
56556 KB |
n = 199991 |
51 |
Correct |
813 ms |
56584 KB |
n = 199993 |
52 |
Correct |
609 ms |
48228 KB |
n = 152076 |
53 |
Correct |
355 ms |
29312 KB |
n = 93249 |
54 |
Correct |
708 ms |
50292 KB |
n = 199910 |
55 |
Correct |
648 ms |
55820 KB |
n = 199999 |
56 |
Correct |
630 ms |
50492 KB |
n = 199997 |
57 |
Correct |
674 ms |
52100 KB |
n = 171294 |
58 |
Correct |
544 ms |
45932 KB |
n = 140872 |
59 |
Correct |
673 ms |
50700 KB |
n = 199886 |
60 |
Correct |
640 ms |
55968 KB |
n = 199996 |
61 |
Correct |
593 ms |
51864 KB |
n = 200000 |
62 |
Correct |
588 ms |
55800 KB |
n = 199998 |
63 |
Correct |
657 ms |
55292 KB |
n = 200000 |
64 |
Correct |
696 ms |
56408 KB |
n = 199998 |
65 |
Correct |
733 ms |
56588 KB |
n = 200000 |
66 |
Correct |
737 ms |
55928 KB |
n = 190000 |
67 |
Correct |
626 ms |
53440 KB |
n = 177777 |
68 |
Correct |
303 ms |
30060 KB |
n = 100000 |
69 |
Correct |
820 ms |
56536 KB |
n = 200000 |
70 |
Correct |
760 ms |
56596 KB |
n = 200000 |
71 |
Correct |
821 ms |
56572 KB |
n = 200000 |
72 |
Correct |
890 ms |
56560 KB |
n = 200000 |
73 |
Correct |
834 ms |
56552 KB |
n = 200000 |
74 |
Correct |
864 ms |
56520 KB |
n = 200000 |
75 |
Correct |
709 ms |
56580 KB |
n = 200000 |
76 |
Correct |
683 ms |
56552 KB |
n = 200000 |
77 |
Correct |
326 ms |
30048 KB |
n = 200000 |
78 |
Correct |
371 ms |
30160 KB |
n = 200000 |
79 |
Correct |
748 ms |
54736 KB |
n = 184307 |
80 |
Correct |
232 ms |
25828 KB |
n = 76040 |
81 |
Correct |
691 ms |
50712 KB |
n = 199981 |
82 |
Correct |
668 ms |
56020 KB |
n = 199994 |
83 |
Correct |
600 ms |
51880 KB |
n = 199996 |
84 |
Correct |
626 ms |
55848 KB |
n = 199998 |
85 |
Correct |
576 ms |
55252 KB |
n = 200000 |
86 |
Correct |
667 ms |
56404 KB |
n = 199998 |
87 |
Correct |
635 ms |
56556 KB |
n = 200000 |
88 |
Correct |
729 ms |
56640 KB |
n = 200000 |
89 |
Correct |
647 ms |
56584 KB |
n = 200000 |
90 |
Correct |
738 ms |
56580 KB |
n = 200000 |
91 |
Correct |
766 ms |
56552 KB |
n = 200000 |
92 |
Correct |
826 ms |
56576 KB |
n = 200000 |