Submission #1321096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321096		kasamchi	Wiring (IOI17_wiring)	C++20	30 / 100	1096 ms	20164 KiB

wiring

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

struct Node {
	long long val, tag;
	Node (void) : val(0), tag(0) {}
};

vector<Node> SEG;

#define L(x) ((x) + (x))
#define R(x) (L(x) + 1)

void push(int id) {
	SEG[L(id)].val += SEG[id].tag;
	SEG[R(id)].val += SEG[id].tag;
	SEG[L(id)].tag += SEG[id].tag;
	SEG[R(id)].tag += SEG[id].tag;
	SEG[id].tag = 0;
}

void mod(int ml, int mr, int l, int r, long long x, int id) {
	if (ml <= l && r <= mr) {
		SEG[id].val += x;
		SEG[id].tag += x;
	} else {
		push(id);
		int m = l + (r - l) / 2;
		if (ml <= m) {
			mod(ml, mr, l, m, x, L(id));
		}
		if (mr > m) {
			mod(ml, mr, m + 1, r, x, R(id));
		}
		SEG[id].val = min(SEG[L(id)].val, SEG[R(id)].val);
	}
}

long long qry(int ql, int qr, int l, int r, int id) {
	if (ql <= l && r <= qr) {
		return SEG[id].val;
	} else {
		push(id);
		int m = l + (r - l) / 2;
		long long ret = 1e18;
		if (ql <= m) {
			ret = min(ret, qry(ql, qr, l, m, L(id)));
		} 
		if (qr > m) {
			ret = min(ret, qry(ql, qr, m + 1, r, R(id)));
		}
		return ret;
	}
}

long long min_total_length(vector<int> r, vector<int> b) {
	int N = r.size() + b.size();
	int ridx = 0, bidx = 0;
	vector<int> pos = {0}, col = {0};
	while (ridx < r.size() || bidx < b.size()) {
		if (bidx == b.size()) {
			pos.push_back(r[ridx]);
			col.push_back(0);
			ridx++;
		} else if (ridx == r.size()) {
			pos.push_back(b[bidx]);
			col.push_back(1);
			bidx++;
		} else if (r[ridx] < b[bidx]) {
			pos.push_back(r[ridx]);
			col.push_back(0);
			ridx++;
		} else {
			pos.push_back(b[bidx]);
			col.push_back(1);
			bidx++;
		}
	}

	vector<pair<int, int>> seg;
	for (int i = 1; i <= N; ) {
		int j = i;
		while (j <= N && col[i] == col[j]) {
			j++;
		}
		seg.push_back(make_pair(i, j - 1));
		i = j;
	}

	vector<long long> pre(N + 1);
	for (int i = 1; i <= N; i++) {
		pre[i] = pre[i - 1] + pos[i];
	}

	vector<long long> dp(N + 1, (long long)1e18);
	SEG.clear(), SEG.resize(N * 4);
	for (int sid = 1; sid < seg.size(); sid++) {
		int clb = seg[sid].first, crb = seg[sid].second;
		int plb = seg[sid - 1].first, prb = seg[sid - 1].second;
		int psz = prb - plb + 1;

		vector<long long> dqb(psz);
		for (int i = 0, p = plb; i < psz; i++, p++) {
			dqb[i] += min(dp[p - 1], dp[p]);
			dqb[i] += pre[p - 1] - pre[plb - 1];
		}

		mod(plb, plb, 1, N, dqb[0], 1);
		for (int i = 1; i < psz; i++) {
			mod(plb + i, plb + i, 1, N, -dqb[i - 1] + dqb[i], 1);
		}

		for (int c = clb; c <= crb; c++) {
			int csz = c - clb + 1;
			long long sum = 0;
			sum += pre[c] - pre[clb - 1];
			sum -= pre[prb] - pre[plb - 1];
			if (psz <= csz) {
				sum -= (long long)pos[prb] * (csz - psz);
			} else {
				sum += (long long)pos[clb] * (psz - csz);
			}

			if (sid == 1) {
				dp[c] = sum;
			} else {
				vector<pair<pair<int, int>, long long>> ops;
				mod(plb, plb, 1, N, sum, 1);
				ops.push_back(make_pair(make_pair(plb, plb), sum));
				if (1 <= psz - csz) {
					mod(plb + 1, plb + (psz - csz), 1, N, -pos[clb], 1);
					ops.push_back(make_pair(make_pair(plb + 1, plb + (psz - csz)), -pos[clb]));
				}
				if (max(0, psz - csz) + 1 < psz) {
					mod(plb + (max(0, psz - csz) + 1), plb + (psz - 1), 1, N, -pos[prb], 1);
					ops.push_back(make_pair(make_pair(plb + (max(0, psz - csz) + 1), plb + (psz - 1)), -pos[prb]));
				}

				int ll = plb, rr = prb + 1;
				while (ll + 1 < rr) {
					int mm = ll + (rr - ll) / 2;
					if (qry(mm, mm, 1, N, 1) < 0) {
						ll = mm;
					} else {
						rr = mm;
					}
				}

				long long cur = 0;
				for (int i = 0, p = plb; p < rr; i++, p++) {
					cur += qry(p, p, 1, N, 1);
					dp[c] = min(dp[c], cur);
				}

				for (auto &[pp, val] : ops) {
					mod(pp.first, pp.second, 1, N, -val, 1);
				}
			}
		}
	}
	return dp[N];
}

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