Submission #588665

#	Time	Username	Problem	Language	Result	Execution time	Memory
588665		dnass	Wiring (IOI17_wiring)	C++17	13 / 100	324 ms	16776 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000LL

lld xx, yy, n;
vector<pair<lld, lld> > a;
vector<lld> dp;

struct item{ //ALTERAR
	lld val;
	item(){
		val = INF;
	}
	item(lld valval){
		val = valval;
	}
};

item merge_neut = item(INF); //ALTERAR

item apply_neut = item(0); //ALTERAR

item merge(item a, item b){ //ALTERAR
	return a.val<b.val?a:b;
}

item apply_lazy(item x, item l, lld len){ //ALTERAR
	return item(x.val+l.val);
}

item apply_lazy_pure(item x, item l){ //ALTERAR
	return item(x.val+l.val);
}

item build_leaf(lld pos){ //ALTERAR
	return item(0);
}

struct ST{

	vector<item> st;
	vector<item> lazy;

	void init(){
		lld sz = 1;
		while(sz<n) sz*=2;
		st.resize(2*sz);
		lazy.resize(2*sz);
	}

	void build(lld v = 1, lld tl = 0, lld tr = n-1){
		if(tl==tr) {
			st[v] = build_leaf(tl);
			lazy[v] = apply_neut;
		}else{
			lld tm = (tl+tr)/2;
			build(2*v, tl, tm);
			build(2*v+1,tm+1,tr);
			st[v] = merge(st[2*v], st[2*v+1]);
			lazy[v] = apply_neut;
		}
	}

	void push(int v, int tl, int tr){
		st[v] = apply_lazy(st[v], lazy[v], tr-tl+1);
		if(tl!=tr){
			lazy[2*v] = apply_lazy_pure(lazy[2*v], lazy[v]);
			lazy[2*v+1] = apply_lazy_pure(lazy[2*v+1], lazy[v]);
		}
		lazy[v] = apply_neut;
	}

	item query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
		push(v, tl, tr);
		if(l>r) return merge_neut;
		if(l<=tl&&tr<=r){
			return st[v];
		}
		lld tm = (tl+tr)/2;
		return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
	}

	void upd(lld l, lld r, item val, lld v=1,lld tl=0, lld tr=n-1){
		push(v,tl,tr);
		if(l>r) return;
 		if(l<=tl&&tr<=r){
 			lazy[v] = apply_lazy_pure(lazy[v], val);
 			push(v,tl,tr);
			return;
 		}
		lld tm = (tl+tr)/2;
		upd(l,min(r,tm), val, 2*v, tl, tm);
		upd(max(l,tm+1),r, val, 2*v+1, tm+1, tr);
		st[v] = merge(st[2*v], st[2*v+1]);
	}

};

ST seg;

lld min_total_length(vector<int> r, vector<int> b){
	xx = (lld) r.size(); yy = (lld) b.size();
	n = xx+yy;
	for(lld i=0;i<xx;i++) a.push_back({r[i], 1});
	for(lld i=0;i<yy;i++) a.push_back({b[i], -1});
	sort(a.begin(), a.end());
	a.push_back({INF, 0});

	dp.resize(n+1); dp[n]=0;

	lld block = 0;
	lld nxt_beg = n, nxt_end = n, this_end = n;
	seg.init(); seg.build();
	for(lld i=n-1;i>=0;i--){
		if(a[i].second!=a[i+1].second){
			block++;
			nxt_beg = i+1;
			nxt_end = this_end;
			this_end = i;
			if(block==1){
				dp[i] = INF;
				continue;
			}
			lld sum_ai = 0;
			for(lld j=nxt_beg;j<=nxt_end;j++){
				sum_ai += a[j].first;
				seg.upd(j, j, sum_ai-(j+1-nxt_beg)*a[i].first+dp[j+1]);
			}
		}else{
			if(block==1){
				dp[i] = INF;
				continue;
			}
			lld pos_block = nxt_beg-i-1;
			seg.upd(nxt_beg, nxt_beg+pos_block-1, a[nxt_beg].first-a[i].first);
			seg.upd(nxt_beg+pos_block, nxt_end, a[nxt_beg-1].first-a[i].first);
		}
		dp[i] = seg.query(nxt_beg, nxt_end).val;
	}
	return dp[0];
}

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