#include <bits/stdc++.h>
#include "wiring.h"
#define pii pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
vector<pii> vec;
long long seg[2][N<<2], dp[N], n, sumr[N], suml[N], lenl[N], lenr[N], pre[N], pos[N];
vector<long long> plug[2];
void update( int t, int pos, long long val, int l = 1, int r = n, int idx = 1 ) {
if( l == r ) return void( seg[t][idx] = val );
int mid = l + r >> 1;
if( pos <= mid ) update( t, pos, val, l, mid, idx<<1 );
else update( t, pos, val, mid + 1, r, idx<<1|1);
seg[t][idx] = min( seg[t][idx<<1], seg[t][idx<<1|1] );
}
long long query( int t, int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
if( ll > rr ) return 1e18;
if( l > rr || r < ll ) return 1e18;
if( l >= ll && r <= rr ) return seg[t][idx];
int mid = l + r >> 1;
return min( query( t, ll, rr, l, mid, idx<<1 ), query( t, ll, rr, mid + 1, r, idx<<1|1 ) );
}
long long min_total_length( vector<int> R, vector<int> B ) {
fill( seg[0], seg[0] + 4*N, 1e18 );
fill( dp, dp + N, 1e18 );
n = R.size() + B.size();
for( int i = 0 ; i < R.size() ; i++ ) plug[0].emplace_back( ( long long )R[i] );
for( int i = 0 ; i < B.size() ; i++ ) plug[1].emplace_back( ( long long )B[i] );
vec.emplace_back( -1e12, -1e12 ), vec.emplace_back( 1e12, 1e12 );
for( int i : R ) vec.emplace_back( i, 0 );
for( int i : B ) vec.emplace_back( i, 1 );
sort( vec.begin(), vec.end() );
for( int i = 1 ; i <= n ; i++ ) {
if( vec[i].y == vec[i-1].y ) {
lenl[i] = lenl[i-1] + 1;
pre[i] = pre[i-1];
suml[i] = suml[i-1] + vec[i].x;
}
else {
lenl[i] = 1;
pre[i] = i;
suml[i] = vec[i].x;
}
}
for( int i = n ; i >= 1 ; i-- ) {
if( vec[i].y == vec[i+1].y ) {
lenr[i] = lenr[i+1] + 1;
pos[i] = pos[i+1];
sumr[i] = sumr[i+1] + vec[i].x;
}
else {
lenr[i] = 1;
pos[i] = i;
sumr[i] = vec[i].x;
}
}
dp[0] = 0;
for( int i = 1 ; i <= n ; i++ ) {
int c = vec[i].y, o = vec[i].y^1;
int idx = lower_bound( plug[o].begin(), plug[o].end(), vec[i].x ) - plug[o].begin();
if( idx != plug[o].size() ) dp[i] = min( dp[i], dp[i-1] + plug[o][idx] - vec[i].x );
if( idx ) dp[i] = min( dp[i], dp[i-1] + vec[i].x - plug[o][idx-1] );
if( pre[i] != 1 ) {
int l = pre[pre[i]-1];
long long mx = vec[pre[i]-1].x;
dp[i] = min( dp[i], query( 0, max( ( long long )l, pre[i] - lenl[i] ), pre[i]-1 ) + suml[i] - 1ll * lenl[i] * mx );
dp[i] = min( dp[i], query( 1, l, pre[i] - lenl[i] - 1 ) + suml[i] - vec[pre[i]].x*lenl[i] );
}
update( 0, i, dp[i-1] - sumr[i] + lenr[i] * vec[pos[i]].x );
update( 1, i, dp[i-1] - sumr[i] + vec[pos[i]+1].x*lenr[i] );
}
return dp[n];
}
Compilation message
wiring.cpp: In function 'void update(int, int, long long int, int, int, int)':
wiring.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wiring.cpp: In function 'long long int query(int, int, int, int, int, int)':
wiring.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:34:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0 ; i < R.size() ; i++ ) plug[0].emplace_back( ( long long )R[i] );
~~^~~~~~~~~~
wiring.cpp:35:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0 ; i < B.size() ; i++ ) plug[1].emplace_back( ( long long )B[i] );
~~^~~~~~~~~~
wiring.cpp:68:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( idx != plug[o].size() ) dp[i] = min( dp[i], dp[i-1] + plug[o][idx] - vec[i].x );
~~~~^~~~~~~~~~~~~~~~~
wiring.cpp:66:13: warning: unused variable 'c' [-Wunused-variable]
int c = vec[i].y, o = vec[i].y^1;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
10 ms |
8184 KB |
Output is correct |
3 |
Correct |
9 ms |
8184 KB |
Output is correct |
4 |
Correct |
9 ms |
8184 KB |
Output is correct |
5 |
Correct |
9 ms |
8184 KB |
Output is correct |
6 |
Correct |
9 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8312 KB |
Output is correct |
9 |
Correct |
10 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8312 KB |
Output is correct |
11 |
Correct |
9 ms |
8184 KB |
Output is correct |
12 |
Correct |
9 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
9 ms |
8184 KB |
Output is correct |
15 |
Correct |
9 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8312 KB |
Output is correct |
3 |
Correct |
122 ms |
25188 KB |
Output is correct |
4 |
Correct |
117 ms |
25188 KB |
Output is correct |
5 |
Correct |
127 ms |
24348 KB |
Output is correct |
6 |
Correct |
200 ms |
28120 KB |
Output is correct |
7 |
Correct |
171 ms |
28120 KB |
Output is correct |
8 |
Correct |
171 ms |
28304 KB |
Output is correct |
9 |
Correct |
160 ms |
28252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8184 KB |
Output is correct |
3 |
Correct |
199 ms |
28128 KB |
Output is correct |
4 |
Correct |
210 ms |
28384 KB |
Output is correct |
5 |
Correct |
9 ms |
8184 KB |
Output is correct |
6 |
Correct |
8 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8184 KB |
Output is correct |
9 |
Correct |
9 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8184 KB |
Output is correct |
11 |
Correct |
9 ms |
8184 KB |
Output is correct |
12 |
Correct |
9 ms |
8152 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
9 ms |
8184 KB |
Output is correct |
15 |
Correct |
9 ms |
8184 KB |
Output is correct |
16 |
Correct |
10 ms |
8184 KB |
Output is correct |
17 |
Correct |
9 ms |
8184 KB |
Output is correct |
18 |
Correct |
210 ms |
28256 KB |
Output is correct |
19 |
Correct |
207 ms |
28384 KB |
Output is correct |
20 |
Correct |
222 ms |
28404 KB |
Output is correct |
21 |
Correct |
202 ms |
28260 KB |
Output is correct |
22 |
Correct |
210 ms |
28256 KB |
Output is correct |
23 |
Correct |
217 ms |
28248 KB |
Output is correct |
24 |
Correct |
215 ms |
28260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
203 ms |
28228 KB |
Output is correct |
3 |
Correct |
193 ms |
28132 KB |
Output is correct |
4 |
Correct |
207 ms |
28128 KB |
Output is correct |
5 |
Correct |
194 ms |
28260 KB |
Output is correct |
6 |
Correct |
9 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8184 KB |
Output is correct |
9 |
Correct |
9 ms |
8184 KB |
Output is correct |
10 |
Correct |
8 ms |
8184 KB |
Output is correct |
11 |
Correct |
9 ms |
8184 KB |
Output is correct |
12 |
Correct |
9 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
9 ms |
8184 KB |
Output is correct |
15 |
Correct |
9 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8184 KB |
Output is correct |
17 |
Correct |
9 ms |
8184 KB |
Output is correct |
18 |
Correct |
216 ms |
28260 KB |
Output is correct |
19 |
Correct |
215 ms |
28380 KB |
Output is correct |
20 |
Correct |
214 ms |
28252 KB |
Output is correct |
21 |
Correct |
212 ms |
28248 KB |
Output is correct |
22 |
Correct |
189 ms |
28256 KB |
Output is correct |
23 |
Correct |
178 ms |
28512 KB |
Output is correct |
24 |
Correct |
202 ms |
28252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
10 ms |
8184 KB |
Output is correct |
3 |
Correct |
9 ms |
8184 KB |
Output is correct |
4 |
Correct |
9 ms |
8184 KB |
Output is correct |
5 |
Correct |
9 ms |
8184 KB |
Output is correct |
6 |
Correct |
9 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8312 KB |
Output is correct |
9 |
Correct |
10 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8312 KB |
Output is correct |
11 |
Correct |
9 ms |
8184 KB |
Output is correct |
12 |
Correct |
9 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
9 ms |
8184 KB |
Output is correct |
15 |
Correct |
9 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8184 KB |
Output is correct |
17 |
Correct |
9 ms |
8184 KB |
Output is correct |
18 |
Correct |
9 ms |
8312 KB |
Output is correct |
19 |
Correct |
122 ms |
25188 KB |
Output is correct |
20 |
Correct |
117 ms |
25188 KB |
Output is correct |
21 |
Correct |
127 ms |
24348 KB |
Output is correct |
22 |
Correct |
200 ms |
28120 KB |
Output is correct |
23 |
Correct |
171 ms |
28120 KB |
Output is correct |
24 |
Correct |
171 ms |
28304 KB |
Output is correct |
25 |
Correct |
160 ms |
28252 KB |
Output is correct |
26 |
Correct |
9 ms |
8184 KB |
Output is correct |
27 |
Correct |
9 ms |
8184 KB |
Output is correct |
28 |
Correct |
199 ms |
28128 KB |
Output is correct |
29 |
Correct |
210 ms |
28384 KB |
Output is correct |
30 |
Correct |
9 ms |
8184 KB |
Output is correct |
31 |
Correct |
8 ms |
8184 KB |
Output is correct |
32 |
Correct |
9 ms |
8184 KB |
Output is correct |
33 |
Correct |
9 ms |
8184 KB |
Output is correct |
34 |
Correct |
9 ms |
8184 KB |
Output is correct |
35 |
Correct |
9 ms |
8184 KB |
Output is correct |
36 |
Correct |
9 ms |
8184 KB |
Output is correct |
37 |
Correct |
9 ms |
8152 KB |
Output is correct |
38 |
Correct |
9 ms |
8184 KB |
Output is correct |
39 |
Correct |
9 ms |
8184 KB |
Output is correct |
40 |
Correct |
9 ms |
8184 KB |
Output is correct |
41 |
Correct |
10 ms |
8184 KB |
Output is correct |
42 |
Correct |
9 ms |
8184 KB |
Output is correct |
43 |
Correct |
210 ms |
28256 KB |
Output is correct |
44 |
Correct |
207 ms |
28384 KB |
Output is correct |
45 |
Correct |
222 ms |
28404 KB |
Output is correct |
46 |
Correct |
202 ms |
28260 KB |
Output is correct |
47 |
Correct |
210 ms |
28256 KB |
Output is correct |
48 |
Correct |
217 ms |
28248 KB |
Output is correct |
49 |
Correct |
215 ms |
28260 KB |
Output is correct |
50 |
Correct |
9 ms |
8184 KB |
Output is correct |
51 |
Correct |
203 ms |
28228 KB |
Output is correct |
52 |
Correct |
193 ms |
28132 KB |
Output is correct |
53 |
Correct |
207 ms |
28128 KB |
Output is correct |
54 |
Correct |
194 ms |
28260 KB |
Output is correct |
55 |
Correct |
9 ms |
8184 KB |
Output is correct |
56 |
Correct |
9 ms |
8184 KB |
Output is correct |
57 |
Correct |
9 ms |
8184 KB |
Output is correct |
58 |
Correct |
9 ms |
8184 KB |
Output is correct |
59 |
Correct |
8 ms |
8184 KB |
Output is correct |
60 |
Correct |
9 ms |
8184 KB |
Output is correct |
61 |
Correct |
9 ms |
8184 KB |
Output is correct |
62 |
Correct |
9 ms |
8184 KB |
Output is correct |
63 |
Correct |
9 ms |
8184 KB |
Output is correct |
64 |
Correct |
9 ms |
8184 KB |
Output is correct |
65 |
Correct |
9 ms |
8184 KB |
Output is correct |
66 |
Correct |
9 ms |
8184 KB |
Output is correct |
67 |
Correct |
216 ms |
28260 KB |
Output is correct |
68 |
Correct |
215 ms |
28380 KB |
Output is correct |
69 |
Correct |
214 ms |
28252 KB |
Output is correct |
70 |
Correct |
212 ms |
28248 KB |
Output is correct |
71 |
Correct |
189 ms |
28256 KB |
Output is correct |
72 |
Correct |
178 ms |
28512 KB |
Output is correct |
73 |
Correct |
202 ms |
28252 KB |
Output is correct |
74 |
Correct |
186 ms |
28256 KB |
Output is correct |
75 |
Correct |
190 ms |
28384 KB |
Output is correct |
76 |
Correct |
186 ms |
28256 KB |
Output is correct |
77 |
Correct |
204 ms |
28260 KB |
Output is correct |
78 |
Correct |
202 ms |
28488 KB |
Output is correct |
79 |
Correct |
195 ms |
28256 KB |
Output is correct |
80 |
Correct |
185 ms |
28260 KB |
Output is correct |
81 |
Correct |
169 ms |
28252 KB |
Output is correct |
82 |
Correct |
168 ms |
28260 KB |
Output is correct |
83 |
Correct |
167 ms |
28248 KB |
Output is correct |
84 |
Correct |
187 ms |
28388 KB |
Output is correct |
85 |
Correct |
207 ms |
28380 KB |
Output is correct |
86 |
Correct |
214 ms |
28256 KB |
Output is correct |
87 |
Correct |
200 ms |
28464 KB |
Output is correct |
88 |
Correct |
191 ms |
28260 KB |
Output is correct |
89 |
Correct |
190 ms |
28388 KB |
Output is correct |
90 |
Correct |
219 ms |
28368 KB |
Output is correct |
91 |
Correct |
180 ms |
28388 KB |
Output is correct |
92 |
Correct |
200 ms |
28252 KB |
Output is correct |
93 |
Correct |
199 ms |
28384 KB |
Output is correct |
94 |
Correct |
210 ms |
28376 KB |
Output is correct |
95 |
Correct |
211 ms |
28256 KB |
Output is correct |
96 |
Correct |
188 ms |
28384 KB |
Output is correct |
97 |
Correct |
185 ms |
28468 KB |
Output is correct |
98 |
Correct |
189 ms |
28260 KB |
Output is correct |
99 |
Correct |
193 ms |
28248 KB |
Output is correct |
100 |
Correct |
213 ms |
28548 KB |
Output is correct |
101 |
Correct |
180 ms |
28252 KB |
Output is correct |
102 |
Correct |
187 ms |
28248 KB |
Output is correct |