Submission #827216

#	Time	Username	Problem	Language	Result	Execution time	Memory
827216		tranxuanbach	Wiring (IOI17_wiring)	C++17	25 / 100	903 ms	231480 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())

using ll = long long;

const ll infll = (ll)1e18 + 7;

const int N = 2e5 + 5;

struct line_container{
	struct line_type{
		ll a, b;
		mutable ll p;
		bool operator< (const line_type& oth) const{
			return a < oth.a;
		}
		bool operator< (ll x) const{
			return p < x;
		}
	};

	multiset <line_type, less<>> mts;
	const ll inf = infll;

	ll div(ll x, ll y){
		return x / y - ((x ^ y) < 0 and x % y);
	}

	template <class T>
	bool isect(T x, T y){
		if (y == mts.end()){
			x->p = infll;
			return false;
		}
		if (x->a == y->a){
			x->p = x->b > y->b ? infll : -infll;
		}
		else{
			x->p = div(y->b - x->b, x->a - y->a);
		}
		return x->p >= y->p;
	}

	void insert(line_type l){
		l.a = -l.a; l.b = -l.b;
		auto z = mts.insert(l), y = z++, x = y;
		while (isect(y, z)){
			z = mts.erase(z);
		}
		if (x != mts.begin() and isect(--x, y)){
			isect(x, mts.erase(y));
		}
		while ((y = x) != mts.begin() and (--x)->p >= y->p){
			isect(x, mts.erase(y));
		}
	}

	ll query(ll x){
		if (mts.empty()){
			return infll;
		}
		auto l = *mts.lower_bound(x);
		return -(l.a * x + l.b);
	}
};

int n, m;
bool col[N];

pair <int, int> pre[N][2];
ll pref[N][2];
ll dp[N];

line_container seg[1 << 19];

void update(int id, int l, int r, int i, const line_container::line_type& ln){
	seg[id].insert(ln);
	if (l == r){
		return;
	}
	int mid = (l + r) >> 1;
	if (i <= mid){
		update(id * 2, l, mid, i, ln);
	}
	else{
		update(id * 2 + 1, mid + 1, r, i, ln);
	}
}

ll query(int id, int l, int r, int u, int v, ll x){
	if (v < l or r < u){
		return infll;
	}
	if (u <= l and r <= v){
		return seg[id].query(x);
	}
	int mid = (l + r) >> 1;
	return min(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x));
}

void update_dp(int i){
	update(1, 0, n + m, i, line_container::line_type{i, dp[i] + (ll)i * (i + 1) / 2});
}

ll min_total_length(vector <int> r, vector <int> b){
	n = isz(r);
	m = isz(b);
	for (auto pos: r){
		col[pos] = true;
	}
	for (auto pos: b){
		col[pos] = false;
	}
	pre[0][0] = pair{0, 0};
	pre[0][1] = pair{0, 0};
	ForE(i, 1, n + m){
		pre[i][0] = pre[i - 1][0];
		pre[i][1] = pre[i - 1][1];
		swap(pre[i][col[i]].fi, pre[i][col[i]].se);
		pre[i][col[i]].fi = i;
	}
	pref[0][0] = 0;
	pref[0][1] = 0;
	ForE(i, 1, n + m){
		pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0);
		pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0);
	}

	fill(dp, dp + n + m + 1, infll);
	dp[0] = 0;
	update_dp(0);
	ForE(i, 1, n + m){
		if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
			continue;
		}
		int j = pre[i][col[i] ^ 1].fi;
		dp[i] = min(dp[i], i - j + dp[i - 1]);
		int k = pre[j][col[i]].fi;
		int leni = i - j, lenj = j - k;
		if (leni <= lenj){
			ll sum = (pref[i][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]);
			int r = j - leni, l = k;
			// cout << l << ' ' << r << ' ' << query(1, 0, n + m, l, r, -(j + 1)) << endl;
			dp[i] = min(dp[i], sum + (ll)r * (j + 1) - (ll)r * (r + 1) / 2 + query(1, 0, n + m, l, r, -(j + 1)));
			// for (int x = j - leni; x >= k; x--){
			// 	dp[i] = min(dp[i], sum + dp[x]);
			// 	sum += (j + 1) - x;
			// }
		}
		// cout << "dp " << i << ' ' << dp[i] << endl;
		update_dp(i);
	}
	return dp[n + m];
}

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