Submission #431530

#	Time	Username	Problem	Language	Result	Execution time	Memory
431530		pliam	Wiring (IOI17_wiring)	C++14	13 / 100	95 ms	11944 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];

void build(int v=1,int start=1,int end=size_seg){
	lazy[v]=0;
	if(start==end){
		int n=start;
		st[v]=dp[pos-1-n]+n*points[pos].first-suff[n];//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.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();
		}
	}
	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
			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);
		}
		dp[pos]=st[1];
	}
	return dp[points.size()-1];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:86: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]
   86 |  for(;pos<points.size();pos++,m++){
      |       ~~~^~~~~~~~~~~~~~

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