Submission #794609

#	Time	Username	Problem	Language	Result	Execution time	Memory
794609		firewater	Wiring (IOI17_wiring)	C++14	100 / 100	140 ms	149448 KiB

wiring

#include "wiring.h"
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include <cassert>
#define ll long long
#define mp make_pair
#define fs first
#define sn second
#define MX 202300
using namespace std;
ll n,w,l,r,sum[MX],num[MX],f[MX],fr[MX];
pair<ll,ll>a[MX];
pair<ll,ll>q[MX];
stack<pair<ll,ll> >d[MX];

ll ask(ll l,ll r)
{
	ll m1,m2,sum1,sum2;
	m1=num[r]-num[l-1];
	m2=r-l+1-m1;
	if(a[l].sn==2)swap(m1,m2);
	sum1=sum[l+m1-1]-sum[l-1];
	sum2=sum[r]-sum[r-m2];
	return ((a[l+m1-1].fs*m1-sum1)+(sum2-a[r-m2+1].fs*m2)+(a[r-m2+1].fs-a[l+m1-1].fs)*max(m1,m2));


}
ll get(ll x,ll y)
{
	return min(f[x-1],f[x])+ask(x,y);
}
long long min_total_length(std::vector<int> R, std::vector<int> B) {
	ll m1=R.size(),m2=B.size();
	for(ll i=1;i<=m1;++i)
		a[i]=mp(R[i-1],1);
	for(ll i=1;i<=m2;++i)
		a[i+m1]=mp(B[i-1],2);
	n=m1+m2;
	sort(a+1,a+1+n);
	for(ll i=1;i<=n;++i){
		if(a[i].sn==1)num[i]=1;
		num[i]+=num[i-1];
		sum[i]=sum[i-1]+a[i].fs;
	}
	l=1;
	for(ll i=1;i<=n;++i){
		fr[i]=w+1;
		if(a[i].sn!=a[i+1].sn){
			q[++w]=mp(l,i);
			l=i+1;
		}
	}
	// for(ll i=1;i<=w;++i)
	// 	printf("%lld %lld\n",q[i].fs,q[i].sn);
	for(ll i=1;i<=n;++i)
		f[i]=100000000000000000ll;
	f[0]=0;
	for(ll i=1;i<=n;++i){
		while(d[fr[i]].size()>0&&d[fr[i]].top().fs<i)d[fr[i]].pop();
		if(d[fr[i]].size()>0)f[i]=get(d[fr[i]].top().sn,i);

		if(fr[i]==w)continue;

		while(d[fr[i]+1].size()>0&&get(i,d[fr[i]+1].top().fs)<get(d[fr[i]+1].top().sn,d[fr[i]+1].top().fs))d[fr[i]+1].pop();
		if(!d[fr[i]+1].size())d[fr[i]+1].push(mp(q[fr[i]+1].sn,i));
		else{
			l=q[fr[i]+1].fs;
			r=d[fr[i]+1].top().fs;
			if(get(i,l)>=get(d[fr[i]+1].top().sn,l))continue;
			while(l<r){
				ll mid=l+r+1>>1;
				if(get(i,mid)<get(d[fr[i]+1].top().sn,mid))l=mid;
				else r=mid-1;
			}
			d[fr[i]+1].push(mp(l,i));
		}
	}
	return f[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     ll mid=l+r+1>>1;
      |            ~~~^~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45