Submission #818031

#	Time	Username	Problem	Language	Result	Execution time	Memory
818031		Temmie	Meetings (IOI18_meetings)	C++17	0 / 100	5533 ms	7240 KiB

meetings

#include <bits/stdc++.h>

int n;
std::vector <int> h, L, R;
std::vector <int> mxl, mxr;

struct Lift {
	std::vector <std::vector <std::pair <int, long long>>> bnl, bnr;
	void init() {
		bnl.resize(19, std::vector <std::pair <int, long long>> (n, { -1, 0 }));
		bnr.resize(19, std::vector <std::pair <int, long long>> (n, { -1, 0 }));
		for (int i = 0; i < n; i++) {
			if (mxl[i] != -1) bnl[0][i] = { mxl[i], (long long) h[mxl[i]] * (i - mxl[i]) };
			if (mxr[i] != -1) bnr[0][i] = { mxr[i], (long long) h[mxr[i]] * (mxr[i] - i) };
		}
		for (int b = 1; b < 19; b++) {
			for (int i = 0; i < n; i++) {
				if (bnl[b - 1][i].first != -1 && bnl[b - 1][bnl[b - 1][i].first].first != -1) {
					bnl[b][i] = {
						bnl[b - 1][bnl[b - 1][i].first].first,
						bnl[b - 1][i].second + bnl[b - 1][bnl[b - 1][i].first].second
					};
				}
				if (bnr[b - 1][i].first != -1 && bnr[b - 1][bnr[b - 1][i].first].first != -1) {
					bnr[b][i] = {
						bnr[b - 1][bnr[b - 1][i].first].first,
						bnr[b - 1][i].second + bnr[b - 1][bnr[b - 1][i].first].second
					};
				}
			}
		}
	}
	long long query(int ind, int l, int r) {
		long long res = h[ind];
		int li = ind, ri = ind;
		for (int b = 18; ~b; b--) {
			if (bnl[b][li].first == -1 || bnl[b][li].first < l) continue;
			res += bnl[b][li].second, li = bnl[b][li].first;
		}
		for (int b = 18; ~b; b--) {
			if (bnr[b][ri].first == -1 || bnr[b][ri].first > r) continue;
			res += bnr[b][ri].second, ri = bnr[b][ri].first;
		}
		if (li != l) res += (long long) (li - l) * h[li];
		if (ri != r) res += (long long) (r - ri) * h[ri];
		return res;
	}
};

Lift lift;

struct Sparse {
	std::vector <std::vector <int>> bin;
	int merge(std::vector <int> i, int l, int r) {
		long long bst = 1LL << 60;
		int ind = -1;
		for (int x : i) {
			long long val = lift.query(x, l, r);
			if (val < bst) bst = val, ind = x;
		}
		return ind;
	}
	void init() {
		bin.resize(19, std::vector <int> (n, -1));
		std::iota(bin[0].begin(), bin[0].end(), 0);
		for (int b = 1; b < 19; b++) {
			for (int i = 0; i + (1 << b) - 1 < n; i++) {
				std::vector <int> ind = {
					bin[b - 1][i],
					bin[b - 1][i + (1 << (b - 1))],
					i + (1 << (b - 1)) - 1,
					i + (1 << (b - 1))
				};
				bin[b][i] = merge(ind, i, i + (1 << b) - 1);
			}
		}
	}
	long long query(int l, int r) {
		if (l == r) return h[l];
		int b = 31 - __builtin_clz(r - l + 1);
		std::vector <int> ind = {
			bin[b][l],
			bin[b][r - (1 << b) + 1],
			l + (1 << b) - 1,
			r - (1 << b) + 1
		};
		int index = merge(ind, l, r);
		return lift.query(index, l, r);
	}
};

Sparse sparse;

std::vector <long long> minimum_costs(std::vector <int> H, std::vector <int> _L, std::vector <int> _R) {
	n = H.size();
	h = H, L = _L, R = _R;
	mxl.resize(n, -1);
	mxr.resize(n, -1);
	std::vector <int> ord(n);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&] (int u, int v) { return h[u] > h[v]; });
	std::set <int> st;
	for (int i : ord) {
		auto it = st.lower_bound(i);
		if (it != st.end()) mxr[i] = *it;
		if (it != st.begin()) mxl[i] = *(--it);
		st.insert(i);
	}
	lift.init();
	// sparse.init();
	std::vector <long long> res(L.size(), -1);
	for (int i = 0; i < (int) L.size(); i++) {
		int l = L[i], r = R[i];
		// res[i] = sparse.query(l, r);
		long long val = 1LL << 60;
		for (int j = l; j <= r; j++) {
			val = std::min(val, lift.query(j, l, r));
		}
		res[i] = val;
	}
	return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40