#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e6+99,inf=1e9+99;
int n,m,cnt,f[N],in[N],out[N],vis[N];
ll ans;
vector<int> ga[N],gb[N];
int getpar(int u){
if(f[u]<0) return u;
return f[u]=getpar(f[u]);
}
void merge(int u,int v,int w=0){
u=getpar(u),v=getpar(v);
if(u==v) return ;
if(f[u]>f[v]) swap(u,v);
f[u]+=f[v];
f[v]=u;
ans+=w;
}
void add(int u,int v,int t){
in[v]+=t;
out[u]+=t;
}
ll plan_roller_coaster(vector<int> s,vector<int> t) {
vector<pair<int,pair<int,int>>> edge;
vector<int> vec;
fill(f,f+N,-1);
f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
sort(all(vec));
vec.resize(unique(all(vec))-vec.begin());
n=vec.size();
f(i,0,s.size()){
int u=lower_bound(all(vec),s[i])-vec.begin(),v=lower_bound(all(vec),t[i])-vec.begin();
merge(u,v);
add(u,v,1);
}
merge(0,n-1);
add(n-1,0,1);
f(i,0,n-1){
if(in[i]==out[i]){
edge.pb({vec[i+1]-vec[i],{i,i+1}});
continue ;
}
merge(i,i+1);
if(in[i]<out[i]){
ans+=1ll*(out[i]-in[i])*(vec[i+1]-vec[i]);
add(i+1,i,out[i]-in[i]);
}
if(in[i]>out[i]){
add(i,i+1,in[i]-out[i]);
}
}
sort(all(edge));
for(auto [w,e] : edge){
merge(e.F,e.S,w);
}
return ans;
}
/*
3
0 5
1 2
3 4
*/
Compilation message
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
52 | f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
| ~~~~~~~~~~~~
railroad.cpp:52:5: note: in expansion of macro 'f'
52 | f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
| ^
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
56 | f(i,0,s.size()){
| ~~~~~~~~~~~~
railroad.cpp:56:5: note: in expansion of macro 'f'
56 | f(i,0,s.size()){
| ^
railroad.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | for(auto [w,e] : edge){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
51172 KB |
n = 2 |
2 |
Correct |
26 ms |
51180 KB |
n = 2 |
3 |
Correct |
26 ms |
51212 KB |
n = 2 |
4 |
Correct |
31 ms |
51152 KB |
n = 2 |
5 |
Correct |
26 ms |
51172 KB |
n = 2 |
6 |
Correct |
27 ms |
51104 KB |
n = 2 |
7 |
Correct |
26 ms |
51156 KB |
n = 3 |
8 |
Correct |
31 ms |
51192 KB |
n = 3 |
9 |
Correct |
31 ms |
51212 KB |
n = 3 |
10 |
Correct |
26 ms |
51100 KB |
n = 8 |
11 |
Correct |
28 ms |
51156 KB |
n = 8 |
12 |
Correct |
26 ms |
51156 KB |
n = 8 |
13 |
Correct |
26 ms |
51184 KB |
n = 8 |
14 |
Correct |
26 ms |
51100 KB |
n = 8 |
15 |
Correct |
28 ms |
51148 KB |
n = 8 |
16 |
Correct |
26 ms |
51180 KB |
n = 8 |
17 |
Correct |
26 ms |
51156 KB |
n = 8 |
18 |
Correct |
29 ms |
51136 KB |
n = 8 |
19 |
Correct |
25 ms |
51152 KB |
n = 3 |
20 |
Correct |
26 ms |
51136 KB |
n = 7 |
21 |
Correct |
26 ms |
51164 KB |
n = 8 |
22 |
Correct |
26 ms |
51156 KB |
n = 8 |
23 |
Correct |
26 ms |
51184 KB |
n = 8 |
24 |
Correct |
26 ms |
51216 KB |
n = 8 |
25 |
Correct |
31 ms |
51132 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
51172 KB |
n = 2 |
2 |
Correct |
26 ms |
51180 KB |
n = 2 |
3 |
Correct |
26 ms |
51212 KB |
n = 2 |
4 |
Correct |
31 ms |
51152 KB |
n = 2 |
5 |
Correct |
26 ms |
51172 KB |
n = 2 |
6 |
Correct |
27 ms |
51104 KB |
n = 2 |
7 |
Correct |
26 ms |
51156 KB |
n = 3 |
8 |
Correct |
31 ms |
51192 KB |
n = 3 |
9 |
Correct |
31 ms |
51212 KB |
n = 3 |
10 |
Correct |
26 ms |
51100 KB |
n = 8 |
11 |
Correct |
28 ms |
51156 KB |
n = 8 |
12 |
Correct |
26 ms |
51156 KB |
n = 8 |
13 |
Correct |
26 ms |
51184 KB |
n = 8 |
14 |
Correct |
26 ms |
51100 KB |
n = 8 |
15 |
Correct |
28 ms |
51148 KB |
n = 8 |
16 |
Correct |
26 ms |
51180 KB |
n = 8 |
17 |
Correct |
26 ms |
51156 KB |
n = 8 |
18 |
Correct |
29 ms |
51136 KB |
n = 8 |
19 |
Correct |
25 ms |
51152 KB |
n = 3 |
20 |
Correct |
26 ms |
51136 KB |
n = 7 |
21 |
Correct |
26 ms |
51164 KB |
n = 8 |
22 |
Correct |
26 ms |
51156 KB |
n = 8 |
23 |
Correct |
26 ms |
51184 KB |
n = 8 |
24 |
Correct |
26 ms |
51216 KB |
n = 8 |
25 |
Correct |
31 ms |
51132 KB |
n = 8 |
26 |
Correct |
27 ms |
51152 KB |
n = 8 |
27 |
Correct |
31 ms |
51208 KB |
n = 8 |
28 |
Correct |
26 ms |
51204 KB |
n = 8 |
29 |
Correct |
31 ms |
51156 KB |
n = 16 |
30 |
Correct |
26 ms |
51168 KB |
n = 16 |
31 |
Correct |
27 ms |
51156 KB |
n = 16 |
32 |
Correct |
27 ms |
51172 KB |
n = 16 |
33 |
Correct |
26 ms |
51176 KB |
n = 16 |
34 |
Correct |
27 ms |
51164 KB |
n = 16 |
35 |
Correct |
27 ms |
51240 KB |
n = 16 |
36 |
Correct |
32 ms |
51148 KB |
n = 15 |
37 |
Correct |
25 ms |
51140 KB |
n = 8 |
38 |
Correct |
25 ms |
51092 KB |
n = 16 |
39 |
Correct |
28 ms |
51168 KB |
n = 16 |
40 |
Correct |
26 ms |
51156 KB |
n = 9 |
41 |
Correct |
27 ms |
51204 KB |
n = 16 |
42 |
Correct |
31 ms |
51156 KB |
n = 16 |
43 |
Correct |
26 ms |
51152 KB |
n = 16 |
44 |
Correct |
26 ms |
51156 KB |
n = 9 |
45 |
Correct |
27 ms |
51132 KB |
n = 15 |
46 |
Correct |
26 ms |
51156 KB |
n = 16 |
47 |
Correct |
25 ms |
51156 KB |
n = 16 |
48 |
Correct |
25 ms |
51068 KB |
n = 16 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
176 ms |
59224 KB |
n = 199999 |
2 |
Correct |
173 ms |
59068 KB |
n = 199991 |
3 |
Correct |
163 ms |
59064 KB |
n = 199993 |
4 |
Correct |
134 ms |
57200 KB |
n = 152076 |
5 |
Correct |
90 ms |
54976 KB |
n = 93249 |
6 |
Correct |
149 ms |
58540 KB |
n = 199910 |
7 |
Correct |
151 ms |
59064 KB |
n = 199999 |
8 |
Correct |
158 ms |
58548 KB |
n = 199997 |
9 |
Correct |
148 ms |
57944 KB |
n = 171294 |
10 |
Correct |
119 ms |
56940 KB |
n = 140872 |
11 |
Correct |
152 ms |
58552 KB |
n = 199886 |
12 |
Correct |
166 ms |
59588 KB |
n = 199996 |
13 |
Correct |
159 ms |
59140 KB |
n = 200000 |
14 |
Correct |
164 ms |
63676 KB |
n = 199998 |
15 |
Correct |
168 ms |
63544 KB |
n = 200000 |
16 |
Correct |
189 ms |
63636 KB |
n = 199998 |
17 |
Correct |
151 ms |
59060 KB |
n = 200000 |
18 |
Correct |
161 ms |
58736 KB |
n = 190000 |
19 |
Correct |
149 ms |
58300 KB |
n = 177777 |
20 |
Correct |
103 ms |
55212 KB |
n = 100000 |
21 |
Correct |
178 ms |
59096 KB |
n = 200000 |
22 |
Correct |
231 ms |
63656 KB |
n = 200000 |
23 |
Correct |
222 ms |
63672 KB |
n = 200000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
51172 KB |
n = 2 |
2 |
Correct |
26 ms |
51180 KB |
n = 2 |
3 |
Correct |
26 ms |
51212 KB |
n = 2 |
4 |
Correct |
31 ms |
51152 KB |
n = 2 |
5 |
Correct |
26 ms |
51172 KB |
n = 2 |
6 |
Correct |
27 ms |
51104 KB |
n = 2 |
7 |
Correct |
26 ms |
51156 KB |
n = 3 |
8 |
Correct |
31 ms |
51192 KB |
n = 3 |
9 |
Correct |
31 ms |
51212 KB |
n = 3 |
10 |
Correct |
26 ms |
51100 KB |
n = 8 |
11 |
Correct |
28 ms |
51156 KB |
n = 8 |
12 |
Correct |
26 ms |
51156 KB |
n = 8 |
13 |
Correct |
26 ms |
51184 KB |
n = 8 |
14 |
Correct |
26 ms |
51100 KB |
n = 8 |
15 |
Correct |
28 ms |
51148 KB |
n = 8 |
16 |
Correct |
26 ms |
51180 KB |
n = 8 |
17 |
Correct |
26 ms |
51156 KB |
n = 8 |
18 |
Correct |
29 ms |
51136 KB |
n = 8 |
19 |
Correct |
25 ms |
51152 KB |
n = 3 |
20 |
Correct |
26 ms |
51136 KB |
n = 7 |
21 |
Correct |
26 ms |
51164 KB |
n = 8 |
22 |
Correct |
26 ms |
51156 KB |
n = 8 |
23 |
Correct |
26 ms |
51184 KB |
n = 8 |
24 |
Correct |
26 ms |
51216 KB |
n = 8 |
25 |
Correct |
31 ms |
51132 KB |
n = 8 |
26 |
Correct |
27 ms |
51152 KB |
n = 8 |
27 |
Correct |
31 ms |
51208 KB |
n = 8 |
28 |
Correct |
26 ms |
51204 KB |
n = 8 |
29 |
Correct |
31 ms |
51156 KB |
n = 16 |
30 |
Correct |
26 ms |
51168 KB |
n = 16 |
31 |
Correct |
27 ms |
51156 KB |
n = 16 |
32 |
Correct |
27 ms |
51172 KB |
n = 16 |
33 |
Correct |
26 ms |
51176 KB |
n = 16 |
34 |
Correct |
27 ms |
51164 KB |
n = 16 |
35 |
Correct |
27 ms |
51240 KB |
n = 16 |
36 |
Correct |
32 ms |
51148 KB |
n = 15 |
37 |
Correct |
25 ms |
51140 KB |
n = 8 |
38 |
Correct |
25 ms |
51092 KB |
n = 16 |
39 |
Correct |
28 ms |
51168 KB |
n = 16 |
40 |
Correct |
26 ms |
51156 KB |
n = 9 |
41 |
Correct |
27 ms |
51204 KB |
n = 16 |
42 |
Correct |
31 ms |
51156 KB |
n = 16 |
43 |
Correct |
26 ms |
51152 KB |
n = 16 |
44 |
Correct |
26 ms |
51156 KB |
n = 9 |
45 |
Correct |
27 ms |
51132 KB |
n = 15 |
46 |
Correct |
26 ms |
51156 KB |
n = 16 |
47 |
Correct |
25 ms |
51156 KB |
n = 16 |
48 |
Correct |
25 ms |
51068 KB |
n = 16 |
49 |
Correct |
176 ms |
59224 KB |
n = 199999 |
50 |
Correct |
173 ms |
59068 KB |
n = 199991 |
51 |
Correct |
163 ms |
59064 KB |
n = 199993 |
52 |
Correct |
134 ms |
57200 KB |
n = 152076 |
53 |
Correct |
90 ms |
54976 KB |
n = 93249 |
54 |
Correct |
149 ms |
58540 KB |
n = 199910 |
55 |
Correct |
151 ms |
59064 KB |
n = 199999 |
56 |
Correct |
158 ms |
58548 KB |
n = 199997 |
57 |
Correct |
148 ms |
57944 KB |
n = 171294 |
58 |
Correct |
119 ms |
56940 KB |
n = 140872 |
59 |
Correct |
152 ms |
58552 KB |
n = 199886 |
60 |
Correct |
166 ms |
59588 KB |
n = 199996 |
61 |
Correct |
159 ms |
59140 KB |
n = 200000 |
62 |
Correct |
164 ms |
63676 KB |
n = 199998 |
63 |
Correct |
168 ms |
63544 KB |
n = 200000 |
64 |
Correct |
189 ms |
63636 KB |
n = 199998 |
65 |
Correct |
151 ms |
59060 KB |
n = 200000 |
66 |
Correct |
161 ms |
58736 KB |
n = 190000 |
67 |
Correct |
149 ms |
58300 KB |
n = 177777 |
68 |
Correct |
103 ms |
55212 KB |
n = 100000 |
69 |
Correct |
178 ms |
59096 KB |
n = 200000 |
70 |
Correct |
231 ms |
63656 KB |
n = 200000 |
71 |
Correct |
222 ms |
63672 KB |
n = 200000 |
72 |
Correct |
185 ms |
59168 KB |
n = 200000 |
73 |
Correct |
178 ms |
59100 KB |
n = 200000 |
74 |
Correct |
190 ms |
59180 KB |
n = 200000 |
75 |
Correct |
171 ms |
63080 KB |
n = 200000 |
76 |
Correct |
163 ms |
63020 KB |
n = 200000 |
77 |
Correct |
145 ms |
61428 KB |
n = 200000 |
78 |
Correct |
176 ms |
65960 KB |
n = 200000 |
79 |
Correct |
155 ms |
61880 KB |
n = 184307 |
80 |
Correct |
77 ms |
55744 KB |
n = 76040 |
81 |
Correct |
154 ms |
61416 KB |
n = 199981 |
82 |
Correct |
157 ms |
62772 KB |
n = 199994 |
83 |
Correct |
159 ms |
62064 KB |
n = 199996 |
84 |
Correct |
204 ms |
66756 KB |
n = 199998 |
85 |
Correct |
183 ms |
66492 KB |
n = 200000 |
86 |
Correct |
176 ms |
67036 KB |
n = 199998 |
87 |
Correct |
166 ms |
62984 KB |
n = 200000 |
88 |
Correct |
166 ms |
63092 KB |
n = 200000 |
89 |
Correct |
159 ms |
63008 KB |
n = 200000 |
90 |
Correct |
160 ms |
63004 KB |
n = 200000 |
91 |
Correct |
193 ms |
67532 KB |
n = 200000 |
92 |
Correct |
205 ms |
67448 KB |
n = 200000 |