Submission #429998

#	Time	Username	Problem	Language	Result	Execution time	Memory
429998		rainboy	Wiring (IOI17_wiring)	C++98	42 / 100	1000 ms	20436 KiB

wiring

#include "wiring.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000, N_ = 1 << 18;	// N_ = pow2(ceil(log2(N + M)))
const int X = 0x3f3f3f3f;

long long min(long long a, long long b) { return a < b ? a : b; }

int sz[N_ * 2]; long long mn[N_ * 2], mx[N_ * 2], sum[N_ * 2], lz2[N_]; char lz1[N_]; int h_, n_;

void put1(int i) {
	mn[i] = mx[i] = sum[i] = 0;
	if (i < n_)
		lz2[i] = 0, lz1[i] = 1;
}

void put2(int i, long long x) {
	mn[i] += x, mx[i] += x, sum[i] += sz[i] * x;
	if (i < n_)
		lz2[i] += x;
}

void pul(int i) {
	if (!lz1[i] && !lz2[i]) {
		mn[i] = mn[i << 1 | 0], mx[i] = mx[i << 1 | 1];
		sum[i] = sum[i << 1 | 0] + sum[i << 1 | 1];
	}
}

void pus(int i) {
	int l = i << 1 | 0, r = i << 1 | 1;

	if (lz1[i])
		put1(l), put1(r), lz1[i] = 0;
	if (lz2[i])
		put2(l, lz2[i]), put2(r, lz2[i]), lz2[i] = 0;
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(int n, int m) {
	int i;

	h_ = 0;
	while (1 << h_ < n + m)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++)
		sz[n_ + i] = 1, mn[n_ + i] = mx[n_ + i] = sum[n_ + i] = i < n ? -X : X;
	for (i = n_ - 1; i > 0; i--)
		pul(i), sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1];
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	if (l > r)
		return;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put2(l++, x);
		if ((r & 1) == 0)
			put2(r--, x);
	}
	pull(l_), pull(r_);
}

long long ans;

void clear_l() {
	int i = 1;

	while (i < n_) {
		pus(i);
		if (mx[i << 1 | 0] < 0) {
			ans += sum[i << 1 | 0], put1(i << 1 | 0);
			i = i << 1 | 1;
		} else
			i = i << 1 | 0;
	}
	if (mx[i] < 0)
		ans += sum[i], put1(i);
	pull(i);
}

void clear_r() {
	int i = 1;

	while (i < n_) {
		pus(i);
		if (mn[i << 1 | 1] > 0) {
			put1(i << 1 | 1);
			i = i << 1 | 0;
		} else
			i = i << 1 | 1;
	}
	if (mn[i] > 0)
		put1(i);
	pull(i);
}

long long min_total_length(vi aa, vi bb) {
	int n = aa.size(), m = bb.size(), i, j, o, x;

	i = 0, j = 0, o = n, x = min(aa[0], bb[0]), ans = (long long) X * n;
	build(n, m);
	while (i < n || j < m) {
		if (i < n && (j == m || aa[i] < bb[j])) {
			update(0, o - 1, x - aa[i]), update(o, n_ - 1, aa[i] - x);
			ans += (long long) (aa[i] - x) * o;
			x = aa[i++], o--;
			clear_r();
		} else {
			update(0, o - 1, x - bb[j]), update(o, n_ - 1, bb[j] - x);
			ans += (long long) (bb[j] - x) * o;
			x = bb[j++], o++;
			clear_l();
		}
	}
	for (i = 1; i < n_; i++)
		pus(i);
	for (i = 0; i < o; i++)
		ans += sum[n_ + i];
	return ans;
}

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