Submission #1061307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061307		vjudge1	Wiring (IOI17_wiring)	C++17	13 / 100	125 ms	23432 KiB

wiring

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long

const ll inf = 1e18;

const int M = 1e5 + 1;

ll seg[M*2],lazy[M*2];
int nn;

void modify(int l,int r,ll x,int v=0,int s=0,int e=nn)
{
	if (l>=e or r<=s)
		return;
	if (l<=s && e<=r)
	{
		lazy[v]+=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=min(seg[lc]+lazy[lc],seg[rc]+lazy[rc]);
}

ll min_total_length(vector<int> r, vector<int> b)
{
	int n=r.size(),m=b.size();
	vector<pair<int,int>> w;
	for (int i=0;i<n;i++)
		w.push_back({r[i],0});
	for (int i=0;i<m;i++)
		w.push_back({b[i],1});
	sort(w.begin(),w.end());
	vector<vector<ll>> v;
	vector<ll> v1={w[0].first};
	map<ll,int> ind;
	ind[w[0].first]=0;
	for (int i=1;i<n+m;i++)
	{
		ind[w[i].first]=i;
		if (w[i].second==w[i-1].second)
			v1.push_back(w[i].first);
		else
			v.push_back(v1),v1={w[i].first};
	}
	v.push_back(v1);
	int k=v.size();
	ll dp[n+m+1];
	dp[0]=0;
	for (int i=1;i<=n+m;i++)
		dp[i]=inf;
	for (int i=1;i<k;i++)
	{
		ll pre=0;
		nn=v[i-1].size();
		for (int j=0;j<=nn*2;j++)
			seg[j]=lazy[j]=0;
		for (int j=nn-1;j>=0;j--)
		{
			pre+=v[i-1][j];
			ll sz=nn-j;
			modify(sz-1,sz,dp[ind[v[i-1][j]]]-pre+v[i][0]*sz);
		}
		dp[ind[v[i][0]]+1]=seg[0]+lazy[0];
		for (int j=1;j<v[i].size();j++)
		{
			modify(0,j,-v[i-1].back());
			modify(0,nn,v[i][j]);
			modify(j,nn,-v[i][0]);
			dp[ind[v[i][j]]+1]=seg[0]+lazy[0];
		}
	}
	return dp[n+m];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int j=1;j<v[i].size();j++)
      |                ~^~~~~~~~~~~~

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