#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,lg=19,kaf=(1<<lg);
long long dp[maxn],inf=1e16,vas[maxn];
long long n,m,ps[maxn],suf[maxn],ghabl[maxn],bad[maxn];
vector<long long>allind;
struct segment{
long long seg[(1<<(lg+1))];
segment(){
for(int i=0;i<(1<<(lg+1));i++){
seg[i]=inf;
}
}
void ins(long long w,int ind){
ind+=kaf;
while(ind>0){
seg[ind]=min(seg[ind],w);
ind>>=1;
}
return ;
}
long long pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return inf;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}seg1,seg2;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
n=(long long)r.size();
m=(long long)b.size();
allind.push_back(-1);
for(auto x:r){
allind.push_back(x);
}
for(auto x:b){
allind.push_back(x);
}
sort(allind.begin(),allind.end());
allind.resize(unique(allind.begin(),allind.end())-allind.begin());
for(long long i=0;i<n;i++){
r[i]=lower_bound(allind.begin(),allind.end(),r[i])-allind.begin();
vas[r[i]]=1;
}
for(long long i=0;i<m;i++){
b[i]=lower_bound(allind.begin(),allind.end(),b[i])-allind.begin();
vas[b[i]]=2;
}
for(long long i=1;i<maxn;i++){
dp[i]=inf;
if((int)allind.size()>i){
ps[i]=ps[i-1]+allind[i];
if(vas[i]!=vas[i-1]){
ghabl[i]=i;
}else{
ghabl[i]=ghabl[i-1];
}
}
}
for(int i=(int)allind.size()-1;i>=1;i--){
suf[i]=suf[i+1]+allind[i];
if(vas[i]!=vas[i+1]){
bad[i]=i;
}else{
bad[i]=bad[i+1];
}
}
dp[0]=0;
allind.push_back(0);
long long sz=(long long)allind.size();
for(long long i=1;i<sz;i++){
long long av=allind[i],unnow=0,last=i,bar=0,akh;
long long ted1=i-ghabl[i]+1;
long long f=(ps[i]-ps[ghabl[i]-1])-(allind[ghabl[i]]*(ted1));
if(ghabl[i]==1){
long long ted2=bad[i]-i+1;
seg1.ins(min(dp[i],dp[i-1])-(suf[i]-suf[bad[i]+1])+(allind[bad[i]]*ted2),i);
seg2.ins(min(dp[i],dp[i-1])-(suf[i]-suf[bad[i]+1])+(allind[bad[i]]*ted2)+ted2*(allind[bad[i]+1]-allind[bad[i]]),i);
continue;
}
long long z=ghabl[ghabl[i]-1];
for(long long j=i-1;j>=1;j--){
if(vas[j]==vas[i]&&vas[j]!=vas[j+1]){
break;
}
if(vas[j]==vas[i]){
last=j;
unnow+=av;
av=allind[j];
}else{
bar+=allind[j];
akh=allind[last-1];
long long ted2=(last-1)-j+1;
//dp[i]=min(dp[i],min(dp[j],dp[j-1])+(ps[i]-ps[last-1])-(allind[last]*ted1)-(suf[j]-suf[last])+(allind[last-1]*ted2)+max(ted1,ted2)*(allind[last]-allind[last-1]));
//dp[i]=min(dp[i],seg.pors(1,0,kaf-1,j,j)+f+max(ted1,ted2)*(allind[last]-allind[last-1]));
if(ted1<ted2){
dp[i]=min(dp[i],seg2.pors(1,0,kaf-1,j,j)+f);
}else{
dp[i]=min(dp[i],seg1.pors(1,0,kaf-1,j,j)+f+ted1*(allind[ghabl[i]]-allind[ghabl[i]-1]));
}
}
}
if(bad[i]==n+m){
continue;
}
long long ted2=bad[i]-i+1;
seg1.ins(min(dp[i],dp[i-1])-(suf[i]-suf[bad[i]+1])+(allind[bad[i]]*ted2),i);
seg2.ins(min(dp[i],dp[i-1])-(suf[i]-suf[bad[i]+1])+(allind[bad[i]]*ted2)+ted2*(allind[bad[i]+1]-allind[bad[i]]),i);
// cout<<i<<" "<<dp[i]<<" "<<vas[i]<<endl;
}
return dp[sz-1];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:79:47: warning: variable 'akh' set but not used [-Wunused-but-set-variable]
79 | long long av=allind[i],unnow=0,last=i,bar=0,akh;
| ^~~
wiring.cpp:88:13: warning: unused variable 'z' [-Wunused-variable]
88 | long long z=ghabl[ghabl[i]-1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
24156 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-6363' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
24156 KB |
3rd lines differ - on the 1st token, expected: '904', found: '-19010' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
24152 KB |
3rd lines differ - on the 1st token, expected: '316', found: '-1902' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
24152 KB |
3rd lines differ - on the 1st token, expected: '27', found: '-6000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
24156 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-6363' |
| 2 |
Halted |
0 ms |
0 KB |
- |
