Submission #1167076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167076		KickingKun	Meetings (IOI18_meetings)	C++20	0 / 100	5593 ms	1708 KiB

meetings

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

#define ll long long

const int N = 1e5 + 2, SQR = 400;

int nxtL[N], nxtR[N];
vector <int> height;
ll dnc(int l, int r, int u, int v) {
	if (u > v) return 1e15;
	if (u == v) {
		int ans = 0;
		for (int i = u; i >= l;) {
			int k = max(l, nxtL[i] + 1);
			ans += height[i] * (i - k + 1);
			i = k - 1;
		}
		for (int i = u; i <= r;) {
			int k = min(r, nxtR[i] - 1);
			ans += height[i] * (k - i + 1);
			i = k + 1;
		}
		return ans -= height[u];
	}
	
	int mid = (l + r) >> 1; ll ans = 1e15;
	vector <int> le, ri;
	for (int i = mid; i >= l; i = nxtL[i])
		le.emplace_back(i);
	reverse(le.begin(), le.end());
	
	for (int i = mid + 1; i <= r; i = nxtR[i])
		ri.emplace_back(i);
	
	int id = ri.size() - 1, sum = 0;
	for (int pos: le) {
		int k = max(nxtL[pos] + 1, l); // k -> pos
		int R = nxtR[pos];
		while (id >= 0 && ri[id] >= R) {
			if (id == ri.size() - 1) sum += (r - ri[id] + 1) * height[ri[id]];
			else sum += (ri[id + 1] - ri[id]) * height[ri[id]];
			--id;
		}
		ans = min(ans, dnc(l, mid, max(k, u), min(pos, v)) + height[pos] * (R - 1 - mid) + sum);
	}
	
	reverse(ri.begin(), ri.end());
	id = 0, sum = 0;
	for (int pos: ri) {
		int k = min(nxtR[pos] - 1, r);
		int L = nxtL[pos];
		while (id < le.size() && le[id] <= L) {
			if (id == 0) sum += (le[id] - l + 1) * height[le[id]];
			else sum += (le[id] - le[id - 1]) * height[le[id]];
			++id;
		}
		ans = min(ans, dnc(mid + 1, r, max(u, pos), min(v, k)) + height[pos] * (mid - L) + sum);
	}
	
	return ans;
}

vector <ll> minimum_costs(vector <int> H, vector <int> L, vector <int> R) {
	assert (*max_element(H.begin(), H.end()) <= 20);
	height = H; int n = H.size(); stack <int> st;
	for (int i = 0; i < n; i++) {
		while (!st.empty() && H[st.top()] <= H[i]) st.pop();
		nxtL[i] = (st.empty() ? -1 : st.top()); st.emplace(i);
	}
	while (!st.empty()) st.pop();
	for (int i = n - 1; i >= 0; i--) {
		while (!st.empty() && H[st.top()] <= H[i]) st.pop();
		nxtR[i] = (st.empty() ? n : st.top()); st.emplace(i);
	}
	
	vector <ll> ans;
	for (int i = 0; i < L.size(); i++)
		ans.emplace_back(dnc(L[i], R[i], L[i], R[i]));
	return ans;
}

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