# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
593174 | yutabi | Wiring (IOI17_wiring) | C++14 | 39 ms | 12632 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair <ll,int> ii;
long long min_total_length(std::vector<int> r, std::vector<int> b)
{
vector <ii> s;
for(int i=0;i<r.size();i++)
{
s.pb(ii(r[i],0));
}
for(int i=0;i<b.size();i++)
{
s.pb(ii(b[i],1));
}
sort(s.begin(),s.end());
vector <ll> L (s.size());
vector <ll> R (s.size());
int last_r=-1;
int last_b=-1;
for(int i=0;i<s.size();i++)
{
if(s[i].second==0)
{
last_r=s[i].first;
L[i]=last_b;
}
else
{
last_b=s[i].first;
L[i]=last_r;
}
}
last_r=-1;
last_b=-1;
for(int i=s.size()-1;i>=0;i--)
{
if(s[i].second==0)
{
last_r=s[i].first;
R[i]=last_b;
}
else
{
last_b=s[i].first;
R[i]=last_r;
}
}
vector <ll> extra_lines;
priority_queue <ll> pq_b;
priority_queue <ll> pq_r;
int el_color=s[0].second;
ll ans=0;
int start;
for(int i=0;s.size();i++)
{
if(s[i].second!=el_color)
{
for(int j=0;j<i-1;j++)
{
extra_lines.pb(s[i].first);
}
start=i+1;
break;
}
ans+=R[i]-s[i].first;
}
//printf("%lld\n",ans);
for(int i=start;i<s.size();i++)
{
if(el_color==s[i].second)
{
extra_lines.clear();
}
if(el_color!=s[i].second && extra_lines.size())
{
ans+=s[i].first-extra_lines.back();
if(s[i].second==0)
{
pq_r.push(s[i].first-extra_lines.back()+s[i].first);
}
else
{
pq_b.push(s[i].first-extra_lines.back()+s[i].first);
}
extra_lines.pop_back();
continue;
}
int taken=0;
if(s[i].second==0)
{
if(pq_b.size())
{
ll num=pq_b.top();
num-=s[i].first;
pq_b.pop();
if(num>-(s[i].first-L[i]))
{
taken++;
ans-=num;
if(num<0)
{
pq_r.push(-num+s[i].first);
}
}
while(pq_b.size() && pq_b.top()-s[i].first>0)
{
num=pq_b.top();
pq_b.pop();
ans-=num;
el_color=1;
extra_lines.pb(s[i].first);
}
}
}
else
{
if(pq_r.size())
{
ll num=pq_r.top();
num-=s[i].first;
pq_r.pop();
if(num>-(s[i].first-L[i]))
{
taken++;
ans-=num;
if(num<0)
{
pq_b.push(-num+s[i].first);
}
}
while(pq_r.size() && pq_r.top()-s[i].first>0)
{
num=pq_r.top();
pq_r.pop();
ans-=num;
el_color=0;
extra_lines.pb(s[i].first);
}
}
}
if(taken==0)
{
ans+=s[i].first-L[i];
if(s[i].second==0)
{
pq_r.push(s[i].first-L[i]+s[i].first);
}
else
{
pq_b.push(s[i].first-L[i]+s[i].first);
}
}
//printf("%d %lld\n",i,ans);
if(i==8)
{
//printf("\n%d %d %d %d %d\n\n",el_color,extra_lines.size(),pq_r.size(),pq_b.size(),L[8]);
}
}
return ans;
}
Compilation message (stderr)
# | 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... |