Submission #264427

#	Time	Username	Problem	Language	Result	Execution time	Memory
264427		arnold518	Wiring (IOI17_wiring)	C++14	100 / 100	389 ms	19576 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

int N, M;
ll A[MAXN+10], B[MAXN+10], D[MAXN+10];
ll ans=0;
pll C[MAXN+10];
ll dp[MAXN+10];
int P[MAXN+10], Q[MAXN+10];

ll tree[MAXN*4+10], lazy[MAXN*4+10];

void busy(int node, int tl, int tr)
{
	if(lazy[node]==0) return;
	tree[node]+=lazy[node];
	if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
	lazy[node]=0;
	return;
}

void update2(int node, int tl, int tr, int p, ll k)
{
	busy(node, tl, tr);
	if(tl==tr) { tree[node]=k; return; }
	int mid=tl+tr>>1;
	if(p<=mid) update2(node*2, tl, mid, p, k);
	else update2(node*2+1, mid+1, tr, p, k);
	tree[node]=min(tree[node*2], tree[node*2+1]);
}

void update(int node, int tl, int tr, int l, int r, ll k)
{
	if(l>r) return;
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
	tree[node]=min(tree[node*2], tree[node*2+1]);
}

ll query(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(l<=tl && tr<=r) return tree[node];
	if(r<tl || tr<l) return INF;
	int mid=tl+tr>>1;
	return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}

ll min_total_length(vector<int> _A, vector<int> _B)
{
	N=_A.size(); M=_B.size();
	for(int i=1; i<=N; i++) A[i]=_A[i-1];
	for(int i=1; i<=M; i++) B[i]=_B[i-1];
	for(int i=1; i<=N; i++) C[i]={A[i], 1};
	for(int i=1; i<=M; i++) C[i+N]={B[i], 2};

	sort(C+1, C+N+M+1);
	
	for(int i=1; i<=N+M; i++) D[i]=D[i-1]+C[i].first;

	P[1]=0;
	for(int i=2; i<=N+M; i++)
	{
		if(C[i].second==C[i-1].second) P[i]=P[i-1];
		else P[i]=i-1;
	}

	int bef;
	for(int i=N+M; i>=1; i--)
	{
		if(C[i].second!=C[i+1].second) bef=i;
		Q[i]=bef;
	}

	ll val=0;
	for(int i=1; i<=N+M; i++)
	{
		dp[i]=1e17;
		if(P[i]==0)
		{
			ll t=C[Q[i]].first*(Q[i]-i+1)-(D[Q[i]]-D[i-1])+dp[i-1]+(Q[i]-i)*(C[Q[i]+1].first-C[Q[i]].first);

			update2(1, 1, N+M, i, t);
			continue;
		}
		if(C[i].second!=C[i-1].second) val=C[i].first-C[i-1].first;
		else val+=C[i].first-C[P[i]].first;
		int l=P[P[i]]+1, r=P[i];

		dp[i]=query(1, 1, N+M, l, r)+val;
		dp[i]=min(dp[i], query(1, 1, N+M, l, l)-dp[l-1]+dp[l]+val);

		update(1, 1, N+M, l, P[i]-(i-P[i]), -(C[r+1].first-C[r].first));
		ll t=C[Q[i]].first*(Q[i]-i+1)-(D[Q[i]]-D[i-1])+dp[i-1]+(Q[i]-i)*(C[Q[i]+1].first-C[Q[i]].first);
		update2(1, 1, N+M, i, t);
	}
	return dp[N+M];
}

Compilation message (stderr)

wiring.cpp: In function 'void update2(int, int, int, int, ll)':
wiring.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid=tl+tr>>1;
      |          ~~^~~
wiring.cpp: In function 'void update(int, int, int, int, int, ll)':
wiring.cpp:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid=tl+tr>>1;
      |          ~~^~~
wiring.cpp: In function 'll query(int, int, int, int, int)':
wiring.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int mid=tl+tr>>1;
      |          ~~^~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:89:7: warning: 'bef' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |   Q[i]=bef;
      |   ~~~~^~~~

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