#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;
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);
}
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);
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 |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
128 ms |
18680 KB |
Output is correct |
4 |
Correct |
128 ms |
19548 KB |
Output is correct |
5 |
Correct |
171 ms |
19192 KB |
Output is correct |
6 |
Correct |
200 ms |
21812 KB |
Output is correct |
7 |
Correct |
199 ms |
22380 KB |
Output is correct |
8 |
Correct |
180 ms |
22856 KB |
Output is correct |
9 |
Correct |
168 ms |
21808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Incorrect |
232 ms |
22044 KB |
3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
302 ms |
21380 KB |
Output is correct |
3 |
Correct |
240 ms |
21300 KB |
Output is correct |
4 |
Correct |
275 ms |
21292 KB |
Output is correct |
5 |
Correct |
239 ms |
21240 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '42', found: '43' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '14694' |
3 |
Halted |
0 ms |
0 KB |
- |