Submission #431729

#	Time	Username	Problem	Language	Result	Execution time	Memory
431729		pliam	Wiring (IOI17_wiring)	C++14	0 / 100	1084 ms	12260 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 100005
#define INF (ll)2e18

ll dp[MAXN+MAXM];
vector<pair<ll,int>> points;//(position,type), r=0, b=1
ll st[4*MAXN];//dp+cost rmq
ll lazy[4*MAXN];
int pos;
int size_seg;
int m;
int prev_col;
ll suff[MAXN];
ll pref[MAXN+MAXM];

ll solve(ll l,ll r,ll f){
	return (pref[r]-pref[f-1])-(pref[f-1]-pref[l-1])+(f-l)*points[f-1].first-(r-f+1)*points[f].first+max(f-l,r-f+1)*(points[f].first-points[f-1].first);
}

ll solve2(int p,int n,int m_){
	return solve(p-m_-n+1,p,p-m_+1);
}

void build(int v=1,int start=1,int end=size_seg){
	lazy[v]=0;
	if(start==end){
		ll n=start;
		st[v]=dp[pos-m-n]+solve2(pos,n,m);//pos is the first of new segment
		return;
	}
	int mid=(start+end)/2;
	build(2*v,start,mid);
	build(2*v+1,mid+1,end);
	st[v]=min(st[2*v],st[2*v+1]);
}

void update(int from,int to,ll val,int v=1,int start=1,int end=size_seg){
	if(start==from&&end==to){
		st[v]+=val;
		lazy[v]+=val;
		return;
	}
	int mid=(start+end)/2;
	if(lazy[v]){//propagate
		update(start,mid,lazy[v],2*v,start,mid);
		update(mid+1,end,lazy[v],2*v+1,mid+1,end);
		lazy[v]=0;
	}
	if(to<=mid){
		update(from,to,val,2*v,start,mid);
	}else if(from>mid){
		update(from,to,val,2*v+1,mid+1,end);
	}else{
		update(from,mid,val,2*v,start,mid);
		update(mid+1,to,val,2*v+1,mid+1,end);
	}
	st[v]=min(st[2*v],st[2*v+1]);
}

ll min_total_length(vector<int> r, vector<int> b) {
	points.clear();
	points.push_back({-1,-1});//numbering from 1, fake point
	//merge sort
	reverse(r.begin(),r.end());
	reverse(b.begin(),b.end());
	while(!r.empty()||!b.empty()){
		if((!r.empty())&&(!b.empty())){
			if(r.back()<b.back()){
				points.push_back({r.back(),0});
				r.pop_back();
			}else{
				points.push_back({b.back(),1});
				b.pop_back();
			}
		}else if(r.empty()){
			points.push_back({b.back(),1});
			b.pop_back();
		}else{
			points.push_back({r.back(),0});
			r.pop_back();
		}
	}
	pref[0]=0;
	for(int i=1;i<points.size();i++){
		assert(points[i].first>=points[i-1].first);
		pref[i]=pref[i-1]+points[i].first;
	}
	dp[0]=0;
	pos=1;
	m=1;
	while(pos==1||prev_col==points[pos].second){
		if(pos==1) prev_col=points[pos].second;
		dp[pos]=INF;
		pos++;
		m++;
	}//found first new segment
	for(;pos<points.size();pos++,m++){
		if(prev_col!=points[pos].second){
			//entered new segment
			prev_col=points[pos].second;
			size_seg=m-1;
			m=1;
			suff[0]=0;
			for(int i=1;i<=size_seg;i++){
				suff[i]=suff[i-1]+points[pos-i].first;
			}
			build();
		}else{
			//existing segment,st needs update
			for(int n=1;n<=size_seg;n++){
				ll dif=solve2(pos,n,m)-solve2(pos-1,n,m-1);
				if(n>=m){
					assert(dif==(points[pos].first-points[pos-m+1].first));
				}else{
					assert(dif==(points[pos].first-points[pos-m].first));
				}
			}
			if(m<=size_seg) update(m,size_seg,points[pos].first-points[pos-m+1].first);
			update(1,min(m-1,size_seg),points[pos].first-points[pos-m].first);
		}
		ll ans=INF;
		for(int n=1;n<=size_seg;n++){
			ans=min(ans,dp[pos-m-n]+solve2(pos,n,m));
		}
		//dp[pos]=st[1];
		dp[pos]=ans;
	}
	return dp[points.size()-1];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=1;i<points.size();i++){
      |              ~^~~~~~~~~~~~~~
wiring.cpp:101:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(;pos<points.size();pos++,m++){
      |       ~~~^~~~~~~~~~~~~~

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