이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)301*1000)
#define INF ((ll)1e16)
ll n,dp[N];
vector <pair<int,bool> > a;
ll seg[4*N],lazy[4*N];
void shift(int id)
{
seg[id*2]+=lazy[id];
seg[id*2+1]+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
void update(int ql,int qr,ll val,int xl=0,int xr=n,int id=1)
{
if(qr<=xl || xr<=ql)return ;
if(ql<=xl && xr<=qr)
{
seg[id]+=val;
lazy[id]+=val;
return ;
}
int mid=(xl+xr)/2;
shift(id);
update(ql,qr,val,xl,mid,id*2);
update(ql,qr,val,mid,xr,id*2+1);
seg[id]=min(seg[id*2],seg[id*2+1]);
}
ll query(int ql,int qr,int xl=0,int xr=n,int id=1)
{
if(qr<=xl || xr<=ql)return INF;
if(ql<=xl && xr<=qr)return seg[id];
int mid=(xl+xr)/2;
shift(id);
return min(query(ql,qr,xl,mid,id*2),query(ql,qr,mid,xr,id*2+1));
}
ll min_total_length(vector<int> r,vector<int> b)
{
for(auto u:r)a.push_back({u,0});
for(auto u:b)a.push_back({u,1});
sort(a.begin(),a.end());
n=a.size();
int i=0;
while(i<n && a[i].second==a[0].second)i++;
int l=0,l2=i;
for(ll j=i-1,sum=0;j>=0;j--)
{
sum+=a[i-1].first-a[j].first+(a[i].first-a[i-1].first);
update(j,j+1,sum+((j>0)?INF:0));
dp[j]=INF;
}
dp[i]=query(l,l2);i++;
//cout<<i-1<<" "<<dp[i-1]<<"\n";
for(;i<n;i++)
{
if(a[i].second==a[l2].second)
{
update(max(l,l2-(i-l2)),l2,a[l2].first-a[l2-1].first);
// cout<<query(l,l2)<<"\n";
update(l,l2,a[i].first-a[l2].first);
dp[i]=query(l,l2);
// cout<<i<<" "<<dp[i]<<"\n";
continue;
}
l=l2;l2=i;
for(ll j=i-1,sum=0;j>=l;j--)
{
sum+=a[i-1].first-a[j].first+(a[i].first-a[i-1].first);
update(j,j+1,sum+dp[j-1]);
}
dp[i]=query(l,l2);
// cout<<i<<" "<<dp[i]<<"\n";
}
return dp[n-1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |