Submission #72897

#	Time	Username	Problem	Language	Result	Execution time	Memory
72897		Sa1378	Wiring (IOI17_wiring)	C++17	100 / 100	340 ms	90140 KiB

wiring

#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+min(dp[j-1],dp[j]));
		}
		dp[i]=query(l,l2);
	//	cout<<i<<" "<<dp[i]<<"\n";
	}
	return dp[n-1];
}

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