#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100000000000000000
struct node{
ll val=0,lz=0;
};
struct SEG{
vector<node>seg;
ll siz=1;
void init(ll n){
while(siz<=n){
siz*=2;
}
seg.resize(2*siz+11);
}
void push(ll id){
seg[id].val+=seg[id].lz;
if(id<=siz){
for(int i=0;i<2;i++){
seg[id*2+i].lz+=seg[id].lz;
}
}
seg[id].lz=0;
}
void upd(ll ul, ll ur, ll l, ll r, ll val, ll id){
push(id);
if(l>ur||r<ul||ul>ur){
return;
}
if(l>=ul&&r<=ur){
seg[id].lz=val;
push(id);
return;
}
ll mid=(l+r)>>1;
upd(ul,ur,l,mid,val,id*2);
upd(ul,ur,mid+1,r,val,id*2+1);
seg[id].val=min(seg[id*2].val,seg[id*2+1].val);
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
push(id);
if(l>qr||r<ql){
return 1e18;
}
if(l>=ql&&r<=qr){
return seg[id].val;
}
ll mid=(l+r)>>1;
return min(qry(ql,qr,l,mid,id*2),qry(ql,qr,mid+1,r,id*2+1));
}
}st;
long long min_total_length(vector<int> r, vector<int> b) {
r.insert(r.begin(), -1);
b.insert(b.begin(),-1);
ll n=r.size()-1,m=b.size()-1;
ll ptrr=0,ptrb=0;
vector<pair<ll,ll> >v;
for(int i=1;i<=n;i++){
v.push_back({r[i],1});
}
for(int i=1;i<=m;i++){
v.push_back({b[i],2});
}
sort(v.begin(),v.end());
v.insert(v.begin(),{-1,-1});
st.init(n+m);
ll stpt[n+m+5],endpt[n+m+5],psum[n+m+5];
psum[0]=0;
stpt[0]=0,endpt[0]=0;
for(int i=1;i<=n+m;i++){
if(i==1){
stpt[i]=i;
}
else{
if(v[i].second==v[i-1].second){
stpt[i]=stpt[i-1];
}
else{
stpt[i]=i;
}
}
psum[i]=psum[i-1]+v[i].first;
}
for(int i=n+m;i>=1;i--){
if(i==n+m){
endpt[i]=i;
}
else{
if(v[i].second==v[i+1].second){
endpt[i]=endpt[i+1];
}
else{
endpt[i]=i;
}
}
}
for(int i=1;i<=n+m;i++){
ll cal=psum[endpt[i]]-psum[i-1];
ll cal2=v[endpt[i]+1].first*(endpt[i]-i);
cal2-=cal;
st.upd(i,i,1,n+m,cal2,1);
}
ll dp[n+m+5];
dp[0]=0;
ll prevupd[n+m+5];
for(int i=1;i<=n+m;i++){
if(stpt[i]==1){
dp[i]=MAX;
st.upd(i+1,i+1,1,n+m,dp[i],1);
prevupd[i+1]=dp[i];
}
else{
ll lol=stpt[i];
ll ini=psum[i]-psum[lol-1];
ll minval=st.qry(stpt[lol-1],lol-1,1,n+m,1);
dp[i]=minval+ini;
st.upd(i+1,i+1,1,n+m,dp[i],1);
prevupd[i+1]=dp[i];
if(prevupd[i]>dp[i]){
st.upd(i,i,1,n+m,dp[i]-prevupd[i],1);
}
ll upds=lol-(i-lol+1);
upds=max(upds,stpt[lol-1]);
ll po=v[lol-1].first;
st.upd(upds,lol-1,1,n+m,-po,1);
st.upd(stpt[lol-1],upds-1,1,n+m,-v[stpt[i]].first,1);
}
}
return dp[n+m];
}
#ifdef LOCAL
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,m;
cin>>n>>m;
vector<int>v,v2;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
v.push_back(x);
}
for(int i=1;i<=m;i++){
ll x;
cin>>x;
v2.push_back(x);
}
cout<<min_total_length(v,v2)<<'\n';
}
#endif
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:58:8: warning: unused variable 'ptrr' [-Wunused-variable]
58 | ll ptrr=0,ptrb=0;
| ^~~~
wiring.cpp:58:15: warning: unused variable 'ptrb' [-Wunused-variable]
58 | ll ptrr=0,ptrb=0;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
388 KB |
Output is correct |
3 |
Correct |
130 ms |
18420 KB |
Output is correct |
4 |
Correct |
129 ms |
19100 KB |
Output is correct |
5 |
Correct |
158 ms |
19452 KB |
Output is correct |
6 |
Correct |
197 ms |
21556 KB |
Output is correct |
7 |
Correct |
200 ms |
22072 KB |
Output is correct |
8 |
Correct |
175 ms |
21880 KB |
Output is correct |
9 |
Correct |
169 ms |
22124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
252 ms |
21560 KB |
Output is correct |
4 |
Correct |
264 ms |
23496 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
600 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
277 ms |
23404 KB |
Output is correct |
19 |
Correct |
244 ms |
23920 KB |
Output is correct |
20 |
Correct |
258 ms |
23604 KB |
Output is correct |
21 |
Correct |
247 ms |
23780 KB |
Output is correct |
22 |
Correct |
263 ms |
23596 KB |
Output is correct |
23 |
Correct |
254 ms |
24212 KB |
Output is correct |
24 |
Correct |
284 ms |
23880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
290 ms |
21668 KB |
Output is correct |
3 |
Correct |
249 ms |
21864 KB |
Output is correct |
4 |
Correct |
273 ms |
21556 KB |
Output is correct |
5 |
Correct |
254 ms |
21556 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
287 ms |
22876 KB |
Output is correct |
19 |
Correct |
284 ms |
23240 KB |
Output is correct |
20 |
Correct |
288 ms |
22812 KB |
Output is correct |
21 |
Correct |
287 ms |
23348 KB |
Output is correct |
22 |
Correct |
248 ms |
23608 KB |
Output is correct |
23 |
Correct |
203 ms |
23904 KB |
Output is correct |
24 |
Correct |
235 ms |
22952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
388 KB |
Output is correct |
19 |
Correct |
130 ms |
18420 KB |
Output is correct |
20 |
Correct |
129 ms |
19100 KB |
Output is correct |
21 |
Correct |
158 ms |
19452 KB |
Output is correct |
22 |
Correct |
197 ms |
21556 KB |
Output is correct |
23 |
Correct |
200 ms |
22072 KB |
Output is correct |
24 |
Correct |
175 ms |
21880 KB |
Output is correct |
25 |
Correct |
169 ms |
22124 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
252 ms |
21560 KB |
Output is correct |
29 |
Correct |
264 ms |
23496 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
0 ms |
600 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
277 ms |
23404 KB |
Output is correct |
44 |
Correct |
244 ms |
23920 KB |
Output is correct |
45 |
Correct |
258 ms |
23604 KB |
Output is correct |
46 |
Correct |
247 ms |
23780 KB |
Output is correct |
47 |
Correct |
263 ms |
23596 KB |
Output is correct |
48 |
Correct |
254 ms |
24212 KB |
Output is correct |
49 |
Correct |
284 ms |
23880 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
290 ms |
21668 KB |
Output is correct |
52 |
Correct |
249 ms |
21864 KB |
Output is correct |
53 |
Correct |
273 ms |
21556 KB |
Output is correct |
54 |
Correct |
254 ms |
21556 KB |
Output is correct |
55 |
Correct |
1 ms |
348 KB |
Output is correct |
56 |
Correct |
0 ms |
348 KB |
Output is correct |
57 |
Correct |
0 ms |
348 KB |
Output is correct |
58 |
Correct |
0 ms |
348 KB |
Output is correct |
59 |
Correct |
0 ms |
348 KB |
Output is correct |
60 |
Correct |
1 ms |
348 KB |
Output is correct |
61 |
Correct |
1 ms |
348 KB |
Output is correct |
62 |
Correct |
0 ms |
348 KB |
Output is correct |
63 |
Correct |
1 ms |
348 KB |
Output is correct |
64 |
Correct |
1 ms |
348 KB |
Output is correct |
65 |
Correct |
1 ms |
348 KB |
Output is correct |
66 |
Correct |
0 ms |
348 KB |
Output is correct |
67 |
Correct |
287 ms |
22876 KB |
Output is correct |
68 |
Correct |
284 ms |
23240 KB |
Output is correct |
69 |
Correct |
288 ms |
22812 KB |
Output is correct |
70 |
Correct |
287 ms |
23348 KB |
Output is correct |
71 |
Correct |
248 ms |
23608 KB |
Output is correct |
72 |
Correct |
203 ms |
23904 KB |
Output is correct |
73 |
Correct |
235 ms |
22952 KB |
Output is correct |
74 |
Correct |
221 ms |
24440 KB |
Output is correct |
75 |
Correct |
240 ms |
23352 KB |
Output is correct |
76 |
Correct |
243 ms |
24372 KB |
Output is correct |
77 |
Correct |
273 ms |
23088 KB |
Output is correct |
78 |
Correct |
246 ms |
23092 KB |
Output is correct |
79 |
Correct |
275 ms |
22840 KB |
Output is correct |
80 |
Correct |
262 ms |
23036 KB |
Output is correct |
81 |
Correct |
211 ms |
23240 KB |
Output is correct |
82 |
Correct |
190 ms |
23108 KB |
Output is correct |
83 |
Correct |
204 ms |
23092 KB |
Output is correct |
84 |
Correct |
229 ms |
23560 KB |
Output is correct |
85 |
Correct |
255 ms |
23604 KB |
Output is correct |
86 |
Correct |
238 ms |
24224 KB |
Output is correct |
87 |
Correct |
233 ms |
23560 KB |
Output is correct |
88 |
Correct |
246 ms |
23824 KB |
Output is correct |
89 |
Correct |
237 ms |
23568 KB |
Output is correct |
90 |
Correct |
275 ms |
23564 KB |
Output is correct |
91 |
Correct |
220 ms |
23700 KB |
Output is correct |
92 |
Correct |
258 ms |
23604 KB |
Output is correct |
93 |
Correct |
231 ms |
23860 KB |
Output is correct |
94 |
Correct |
254 ms |
23540 KB |
Output is correct |
95 |
Correct |
280 ms |
24124 KB |
Output is correct |
96 |
Correct |
220 ms |
24120 KB |
Output is correct |
97 |
Correct |
217 ms |
24140 KB |
Output is correct |
98 |
Correct |
231 ms |
24312 KB |
Output is correct |
99 |
Correct |
234 ms |
23624 KB |
Output is correct |
100 |
Correct |
278 ms |
24356 KB |
Output is correct |
101 |
Correct |
212 ms |
24632 KB |
Output is correct |
102 |
Correct |
234 ms |
23604 KB |
Output is correct |