Submission #72939

#	Time	Username	Problem	Language	Result	Execution time	Memory
72939		mr_banana	Wiring (IOI17_wiring)	C++17	100 / 100	320 ms	18484 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=2e5+100;
const long long inf=1e15;
long long dp[MN];
long long seg[4*MN],lazy[4*MN];
int bck[MN],fr[MN];
long cbck[MN],cfr[MN];
int n,len,m;
void shift(int v){
	seg[2*v]+=lazy[v];
	lazy[2*v]+=lazy[v];
	seg[2*v+1]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[v]=0;
}
void add(int l,int r,long long val,int v=1,int s=0,int e=len+1){
	if(l<=s && e<=r){
		seg[v]+=val;
		lazy[v]+=val;
		return;
	}
	if(l>=e || s>=r){
		return;
	}
	shift(v);
	int mid=(s+e)/2;
	add(l,r,val,2*v,s,mid);
	add(l,r,val,2*v+1,mid,e);
	seg[v]=min(seg[2*v],seg[2*v+1]);
}
void st(int p,long long val,int v=1,int s=0,int e=len+1){
	if(e-s<2){
		seg[v]=min(seg[v],val);
		return;
	}
	shift(v);
	int mid=(s+e)/2;
	if(p<mid){
		st(p,val,2*v,s,mid);
	}
	else{
		st(p,val,2*v+1,mid,e);
	}
}
long long get(int l,int r,int v=1,int s=0,int e=len+1){
	if(l<=s && e<=r){
		return seg[v];
	}
	if(l>=e || s>=r){
		return inf;
	}
	shift(v);
	int mid=(s+e)/2;
	return min(get(l,r,2*v,s,mid),get(l,r,2*v+1,mid,e));
}
long long min_total_length(vector<int> r, vector<int> b) {
	n=r.size(),m=b.size();
	vector<pair<int,int>> po;
	for(int i:r){
		po.push_back({i,0});
	}
	for(int i:b){
		po.push_back({i,1});
	}
	sort(po.begin(),po.end());
	len=n+m;
	for(int i=0;i<len;i++){
		if(i>0 && po[i-1].second==po[i].second){
			bck[i]=bck[i-1];
			cbck[i]=cbck[i-1]+po[i].first-po[bck[i]].first;
		}
		else{
			bck[i]=i;
			cbck[i]=0;
		}
	}
	for(int i=len-1;i>=0;i--){
		if(i+1<len && po[i+1].second==po[i].second){
			fr[i]=fr[i+1];
			cfr[i]=cfr[i+1]+po[fr[i]].first-po[i].first;
		}
		else{
			fr[i]=i;
			cfr[i]=0;
		}
	}
	dp[0]=0;
	add(0,1,dp[0]+cfr[0]+1ll*(po[fr[0]+1].first-po[fr[0]].first)*(fr[0]+1));
	for(int i=0;i<len;i++){
		int x=bck[i];
		if(x==0){
			dp[i+1]=inf;
		}
		else{
			int y=bck[x-1];
			add(max(2*x-i,y),x,po[x].first-po[x-1].first);
			dp[i+1]=get(y,x)+cbck[i];
		}
		if(fr[i+1]+1<len){
			add(i+1,i+2,dp[i+1]+cfr[i+1]+1ll*(fr[i+1]-i)*(po[fr[i+1]+1].first-po[fr[i+1]].first));
		}
		if(fr[i]==bck[i] && fr[i]+1<len){
			st(i,dp[i+1]+po[fr[i]+1].first-po[fr[i]].first);
		}
	}
	return dp[len];
}

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