#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
struct point
{
int pos, id, ty;
point() {}
point(int a, int b, int c)
{
pos=a;
id=b;
ty=c;
}
};
bool cmp(point p, point q)
{
return p.pos<q.pos;
}
int n;
int poss[200005], post[200005];
vector<int> gr[400005];
point p[400005];
int brt=0;
int tree[400005];
void dfs(int v)
{
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(!tree[nv])
{
tree[nv]=brt;
dfs(nv);
}
}
}
int par[400005];
int dp[400005];
vector<pair<int, pair<int, int> > > edges;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
s.push_back(1000000005);
t.push_back(1);
n=s.size();
for(int i=0; i<n; i++)
{
p[2*i]=point(s[i], i, 1);
p[2*i+1]=point(t[i], i, -1);
}
sort(p, p+2*n, cmp);
long long ans=0;
long long sm=0;
for(int i=0; i<2*n; i++)
{
if(p[i].ty==-1) poss[p[i].id]=i;
if(p[i].ty==1) post[p[i].id]=i;
}
for(int i=0; i<n; i++) gr[poss[i]].push_back(post[i]);
for(int i=0; i<2*n; i++)
{
sm+=p[i].ty;
if(i && p[i].pos==p[i-1].pos) {gr[i-1].push_back(i); gr[i].push_back(i-1);}
if(sm>0) {ans+=sm*(p[i+1].pos-p[i].pos); gr[i+1].push_back(i); gr[i].push_back(i+1);}
if(sm<0) {gr[i+1].push_back(i); gr[i].push_back(i+1);}
}
for(int i=0; i<2*n; i++)
{
if(!tree[i])
{
brt++;
tree[i]=brt;
dfs(i);
}
}
///cout<<ans<<endl;
for(int i=1; i<=brt; i++) {par[i]=i; dp[i]=1;}
for(int i=0; i<2*n-1; i++)
{
if(tree[i]==tree[i+1]) continue;
edges.push_back({p[i+1].pos-p[i].pos,{tree[i], tree[i+1]}});
}
sort(edges.begin(), edges.end());
int m=edges.size();
for(int i=0; i<m; i++)
{
int v1=edges[i].second.first, v2=edges[i].second.second;
while(v1!=par[v1]) v1=par[v1];
while(v2!=par[v2]) v2=par[v2];
if(v1==v2) continue;
ans+=edges[i].first;
if(dp[v1]>dp[v2]) par[v2]=v1;
else if(dp[v1]<dp[v2]) par[v1]=v2;
else
{
par[v1]=v2;
dp[v2]++;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9700 KB |
n = 2 |
2 |
Correct |
4 ms |
9684 KB |
n = 2 |
3 |
Correct |
4 ms |
9700 KB |
n = 2 |
4 |
Correct |
4 ms |
9684 KB |
n = 2 |
5 |
Correct |
4 ms |
9720 KB |
n = 2 |
6 |
Correct |
4 ms |
9684 KB |
n = 2 |
7 |
Correct |
4 ms |
9684 KB |
n = 3 |
8 |
Correct |
5 ms |
9684 KB |
n = 3 |
9 |
Correct |
5 ms |
9704 KB |
n = 3 |
10 |
Correct |
5 ms |
9684 KB |
n = 8 |
11 |
Correct |
4 ms |
9684 KB |
n = 8 |
12 |
Correct |
4 ms |
9708 KB |
n = 8 |
13 |
Correct |
4 ms |
9684 KB |
n = 8 |
14 |
Correct |
4 ms |
9708 KB |
n = 8 |
15 |
Correct |
5 ms |
9684 KB |
n = 8 |
16 |
Correct |
4 ms |
9716 KB |
n = 8 |
17 |
Correct |
5 ms |
9684 KB |
n = 8 |
18 |
Correct |
5 ms |
9684 KB |
n = 8 |
19 |
Correct |
4 ms |
9700 KB |
n = 3 |
20 |
Correct |
4 ms |
9704 KB |
n = 7 |
21 |
Correct |
4 ms |
9684 KB |
n = 8 |
22 |
Correct |
4 ms |
9684 KB |
n = 8 |
23 |
Correct |
4 ms |
9684 KB |
n = 8 |
24 |
Correct |
4 ms |
9704 KB |
n = 8 |
25 |
Correct |
5 ms |
9684 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9700 KB |
n = 2 |
2 |
Correct |
4 ms |
9684 KB |
n = 2 |
3 |
Correct |
4 ms |
9700 KB |
n = 2 |
4 |
Correct |
4 ms |
9684 KB |
n = 2 |
5 |
Correct |
4 ms |
9720 KB |
n = 2 |
6 |
Correct |
4 ms |
9684 KB |
n = 2 |
7 |
Correct |
4 ms |
9684 KB |
n = 3 |
8 |
Correct |
5 ms |
9684 KB |
n = 3 |
9 |
Correct |
5 ms |
9704 KB |
n = 3 |
10 |
Correct |
5 ms |
9684 KB |
n = 8 |
11 |
Correct |
4 ms |
9684 KB |
n = 8 |
12 |
Correct |
4 ms |
9708 KB |
n = 8 |
13 |
Correct |
4 ms |
9684 KB |
n = 8 |
14 |
Correct |
4 ms |
9708 KB |
n = 8 |
15 |
Correct |
5 ms |
9684 KB |
n = 8 |
16 |
Correct |
4 ms |
9716 KB |
n = 8 |
17 |
Correct |
5 ms |
9684 KB |
n = 8 |
18 |
Correct |
5 ms |
9684 KB |
n = 8 |
19 |
Correct |
4 ms |
9700 KB |
n = 3 |
20 |
Correct |
4 ms |
9704 KB |
n = 7 |
21 |
Correct |
4 ms |
9684 KB |
n = 8 |
22 |
Correct |
4 ms |
9684 KB |
n = 8 |
23 |
Correct |
4 ms |
9684 KB |
n = 8 |
24 |
Correct |
4 ms |
9704 KB |
n = 8 |
25 |
Correct |
5 ms |
9684 KB |
n = 8 |
26 |
Correct |
5 ms |
9736 KB |
n = 8 |
27 |
Correct |
6 ms |
9700 KB |
n = 8 |
28 |
Correct |
5 ms |
9684 KB |
n = 8 |
29 |
Correct |
5 ms |
9684 KB |
n = 16 |
30 |
Correct |
4 ms |
9704 KB |
n = 16 |
31 |
Correct |
4 ms |
9684 KB |
n = 16 |
32 |
Correct |
5 ms |
9704 KB |
n = 16 |
33 |
Correct |
4 ms |
9684 KB |
n = 16 |
34 |
Correct |
5 ms |
9684 KB |
n = 16 |
35 |
Correct |
4 ms |
9684 KB |
n = 16 |
36 |
Correct |
5 ms |
9684 KB |
n = 15 |
37 |
Correct |
5 ms |
9684 KB |
n = 8 |
38 |
Correct |
4 ms |
9704 KB |
n = 16 |
39 |
Correct |
4 ms |
9684 KB |
n = 16 |
40 |
Correct |
4 ms |
9704 KB |
n = 9 |
41 |
Correct |
4 ms |
9636 KB |
n = 16 |
42 |
Correct |
4 ms |
9684 KB |
n = 16 |
43 |
Correct |
5 ms |
9692 KB |
n = 16 |
44 |
Correct |
4 ms |
9684 KB |
n = 9 |
45 |
Correct |
4 ms |
9684 KB |
n = 15 |
46 |
Correct |
4 ms |
9684 KB |
n = 16 |
47 |
Correct |
4 ms |
9704 KB |
n = 16 |
48 |
Correct |
6 ms |
9700 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
55832 KB |
n = 199999 |
2 |
Correct |
190 ms |
47852 KB |
n = 199991 |
3 |
Correct |
151 ms |
47204 KB |
n = 199993 |
4 |
Correct |
127 ms |
37468 KB |
n = 152076 |
5 |
Correct |
71 ms |
27228 KB |
n = 93249 |
6 |
Correct |
155 ms |
43016 KB |
n = 199910 |
7 |
Correct |
185 ms |
45772 KB |
n = 199999 |
8 |
Correct |
171 ms |
45392 KB |
n = 199997 |
9 |
Correct |
143 ms |
41084 KB |
n = 171294 |
10 |
Correct |
114 ms |
35536 KB |
n = 140872 |
11 |
Correct |
155 ms |
43168 KB |
n = 199886 |
12 |
Correct |
157 ms |
45592 KB |
n = 199996 |
13 |
Correct |
167 ms |
45348 KB |
n = 200000 |
14 |
Correct |
169 ms |
50904 KB |
n = 199998 |
15 |
Correct |
196 ms |
48212 KB |
n = 200000 |
16 |
Correct |
192 ms |
47824 KB |
n = 199998 |
17 |
Correct |
156 ms |
46424 KB |
n = 200000 |
18 |
Correct |
158 ms |
48988 KB |
n = 190000 |
19 |
Correct |
141 ms |
50648 KB |
n = 177777 |
20 |
Correct |
86 ms |
28092 KB |
n = 100000 |
21 |
Correct |
203 ms |
46936 KB |
n = 200000 |
22 |
Correct |
186 ms |
41184 KB |
n = 200000 |
23 |
Correct |
220 ms |
55880 KB |
n = 200000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9700 KB |
n = 2 |
2 |
Correct |
4 ms |
9684 KB |
n = 2 |
3 |
Correct |
4 ms |
9700 KB |
n = 2 |
4 |
Correct |
4 ms |
9684 KB |
n = 2 |
5 |
Correct |
4 ms |
9720 KB |
n = 2 |
6 |
Correct |
4 ms |
9684 KB |
n = 2 |
7 |
Correct |
4 ms |
9684 KB |
n = 3 |
8 |
Correct |
5 ms |
9684 KB |
n = 3 |
9 |
Correct |
5 ms |
9704 KB |
n = 3 |
10 |
Correct |
5 ms |
9684 KB |
n = 8 |
11 |
Correct |
4 ms |
9684 KB |
n = 8 |
12 |
Correct |
4 ms |
9708 KB |
n = 8 |
13 |
Correct |
4 ms |
9684 KB |
n = 8 |
14 |
Correct |
4 ms |
9708 KB |
n = 8 |
15 |
Correct |
5 ms |
9684 KB |
n = 8 |
16 |
Correct |
4 ms |
9716 KB |
n = 8 |
17 |
Correct |
5 ms |
9684 KB |
n = 8 |
18 |
Correct |
5 ms |
9684 KB |
n = 8 |
19 |
Correct |
4 ms |
9700 KB |
n = 3 |
20 |
Correct |
4 ms |
9704 KB |
n = 7 |
21 |
Correct |
4 ms |
9684 KB |
n = 8 |
22 |
Correct |
4 ms |
9684 KB |
n = 8 |
23 |
Correct |
4 ms |
9684 KB |
n = 8 |
24 |
Correct |
4 ms |
9704 KB |
n = 8 |
25 |
Correct |
5 ms |
9684 KB |
n = 8 |
26 |
Correct |
5 ms |
9736 KB |
n = 8 |
27 |
Correct |
6 ms |
9700 KB |
n = 8 |
28 |
Correct |
5 ms |
9684 KB |
n = 8 |
29 |
Correct |
5 ms |
9684 KB |
n = 16 |
30 |
Correct |
4 ms |
9704 KB |
n = 16 |
31 |
Correct |
4 ms |
9684 KB |
n = 16 |
32 |
Correct |
5 ms |
9704 KB |
n = 16 |
33 |
Correct |
4 ms |
9684 KB |
n = 16 |
34 |
Correct |
5 ms |
9684 KB |
n = 16 |
35 |
Correct |
4 ms |
9684 KB |
n = 16 |
36 |
Correct |
5 ms |
9684 KB |
n = 15 |
37 |
Correct |
5 ms |
9684 KB |
n = 8 |
38 |
Correct |
4 ms |
9704 KB |
n = 16 |
39 |
Correct |
4 ms |
9684 KB |
n = 16 |
40 |
Correct |
4 ms |
9704 KB |
n = 9 |
41 |
Correct |
4 ms |
9636 KB |
n = 16 |
42 |
Correct |
4 ms |
9684 KB |
n = 16 |
43 |
Correct |
5 ms |
9692 KB |
n = 16 |
44 |
Correct |
4 ms |
9684 KB |
n = 9 |
45 |
Correct |
4 ms |
9684 KB |
n = 15 |
46 |
Correct |
4 ms |
9684 KB |
n = 16 |
47 |
Correct |
4 ms |
9704 KB |
n = 16 |
48 |
Correct |
6 ms |
9700 KB |
n = 16 |
49 |
Correct |
163 ms |
55832 KB |
n = 199999 |
50 |
Correct |
190 ms |
47852 KB |
n = 199991 |
51 |
Correct |
151 ms |
47204 KB |
n = 199993 |
52 |
Correct |
127 ms |
37468 KB |
n = 152076 |
53 |
Correct |
71 ms |
27228 KB |
n = 93249 |
54 |
Correct |
155 ms |
43016 KB |
n = 199910 |
55 |
Correct |
185 ms |
45772 KB |
n = 199999 |
56 |
Correct |
171 ms |
45392 KB |
n = 199997 |
57 |
Correct |
143 ms |
41084 KB |
n = 171294 |
58 |
Correct |
114 ms |
35536 KB |
n = 140872 |
59 |
Correct |
155 ms |
43168 KB |
n = 199886 |
60 |
Correct |
157 ms |
45592 KB |
n = 199996 |
61 |
Correct |
167 ms |
45348 KB |
n = 200000 |
62 |
Correct |
169 ms |
50904 KB |
n = 199998 |
63 |
Correct |
196 ms |
48212 KB |
n = 200000 |
64 |
Correct |
192 ms |
47824 KB |
n = 199998 |
65 |
Correct |
156 ms |
46424 KB |
n = 200000 |
66 |
Correct |
158 ms |
48988 KB |
n = 190000 |
67 |
Correct |
141 ms |
50648 KB |
n = 177777 |
68 |
Correct |
86 ms |
28092 KB |
n = 100000 |
69 |
Correct |
203 ms |
46936 KB |
n = 200000 |
70 |
Correct |
186 ms |
41184 KB |
n = 200000 |
71 |
Correct |
220 ms |
55880 KB |
n = 200000 |
72 |
Correct |
189 ms |
55764 KB |
n = 200000 |
73 |
Correct |
223 ms |
47940 KB |
n = 200000 |
74 |
Correct |
165 ms |
45472 KB |
n = 200000 |
75 |
Correct |
164 ms |
55844 KB |
n = 200000 |
76 |
Correct |
156 ms |
55728 KB |
n = 200000 |
77 |
Correct |
172 ms |
55844 KB |
n = 200000 |
78 |
Correct |
225 ms |
41756 KB |
n = 200000 |
79 |
Correct |
170 ms |
44380 KB |
n = 184307 |
80 |
Correct |
57 ms |
24084 KB |
n = 76040 |
81 |
Correct |
159 ms |
43216 KB |
n = 199981 |
82 |
Correct |
155 ms |
45656 KB |
n = 199994 |
83 |
Correct |
159 ms |
45356 KB |
n = 199996 |
84 |
Correct |
154 ms |
50892 KB |
n = 199998 |
85 |
Correct |
157 ms |
48240 KB |
n = 200000 |
86 |
Correct |
158 ms |
47952 KB |
n = 199998 |
87 |
Correct |
141 ms |
46376 KB |
n = 200000 |
88 |
Correct |
159 ms |
51032 KB |
n = 200000 |
89 |
Correct |
142 ms |
55776 KB |
n = 200000 |
90 |
Correct |
178 ms |
46892 KB |
n = 200000 |
91 |
Correct |
175 ms |
41160 KB |
n = 200000 |
92 |
Correct |
242 ms |
55852 KB |
n = 200000 |