Submission #598066

#	Time	Username	Problem	Language	Result	Execution time	Memory
598066		Lucpp	Wiring (IOI17_wiring)	C++17	100 / 100	294 ms	16704 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) ((int)(x).size())
const ll INF = 1e18;

int cap;
vector<ll> seg, lazy;
void init(int n){
	for(cap=1; cap < n; cap*=2);
	seg.assign(2*cap, INF);
	lazy.assign(2*cap, 0);
}
void push(int i){
	seg[2*i] += lazy[i];
	lazy[2*i] += lazy[i];
	seg[2*i+1] += lazy[i];
	lazy[2*i+1] += lazy[i];
	lazy[i] = 0;
}
void add(int l, int r, ll v, int a, int b, int i){
	if(l <= a && b <= r){
		seg[i] += v;
		lazy[i] += v;
	}
	else if(b < l || r < a) return;
	else{
		push(i);
		int m = (a+b)/2;
		add(l, r, v, a, m, 2*i);
		add(l, r, v, m+1, b, 2*i+1);
		seg[i] = min(seg[2*i], seg[2*i+1]);
	}
}
void upd(int p, ll v, int a, int b, int i){
	if(a == b) seg[i] = v;
	else{
		push(i);
		int m = (a+b)/2;
		if(p <= m) upd(p, v, a, m, 2*i);
		else upd(p, v, m+1, b, 2*i+1);
	}
}
ll qry(int l, int r, int a, int b, int i){
	if(l <= a && b <= r) return seg[i];
	if(b < l || r < a) return INF;
	push(i);
	int m = (a+b)/2;
	return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}

struct Block{
	int col, cnt, first, last;
	Block(int _col, int _cnt, int _first, int _last): col(_col), cnt(_cnt), first(_first), last(_last){}
};

ll min_total_length(vector<int> r, vector<int> b) {
	int n = int(r.size()), m = int(b.size());
	vector<pair<int, int>> a;
	for(int i : r) a.emplace_back(i, 0);
	for(int i : b) a.emplace_back(i, 1);
	sort(a.begin(), a.end());
	vector<ll> dp(n+m+1, INF);
	dp[0] = 0;
	init(n+m+1);
	upd(1, 0, 1, cap, 1);
	vector<Block> blocks;
	bool three = false;
	blocks.emplace_back(a[0].second, 1, 0, 0);
	for(int i = 0; i < n+m; i++){
		if(blocks.back().col == a[i].second){
			if(blocks.size() != 1){
				if(three){
					dp[i+1] = dp[i] + a[i].first-a[blocks[sz(blocks)-2].last].first;
				}
				else{
					ll small = a[i].first-a[blocks[sz(blocks)-1].first].first;
					ll big = a[i].first-a[blocks[sz(blocks)-2].last].first;
					int j = blocks[sz(blocks)-2].last - blocks[sz(blocks)-1].cnt;
					Block bl = blocks[sz(blocks)-2];
					j = max(j, bl.first-1);
					add(j+2, bl.last+1, big, 1, cap, 1);
					add(bl.first+1, j+1, small, 1, cap, 1);
					dp[i+1] = qry(bl.first+1, bl.last+1, 1, cap, 1);
				}
			}
			blocks.back().cnt++;
			blocks.back().last = i;
		}
		else{
			three = (int)blocks.size() > 1 && blocks.back().cnt == 1;
			if(three){
				dp[i+1] = min(dp[i], dp[i-1]) + a[i].first-a[blocks[sz(blocks)-1].last].first;
			}
			else{
				ll cost = 0;
				for(int j = blocks.back().last; j >= blocks.back().first; j--){
					cost += a[i].first-a[j].first;
					add(j+1, j+1, cost, 1, cap, 1);
				}
				dp[i+1] = qry(blocks.back().first+1, blocks.back().last+1, 1, cap, 1);
			}
			blocks.emplace_back(a[i].second, 1, i, i);
		}
		if(dp[i+1] >= INF) continue;
		upd(i+2, dp[i+1], 1, cap, 1);
	}
	return dp[n+m];
}

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