Submission #1167330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167330		KickingKun	Meetings (IOI18_meetings)	C++20	41 / 100	2723 ms	356656 KiB

meetings

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

#define ll long long

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

int nxtL[N], nxtR[N];
vector <int> height;

int cost(int l, int r, int u) {
	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 cache[SQR + 1][N];
int dnc(int l, int r) {
	if (l > r) return 1e9;
	if (l == r) return height[l];
	if (r - l <= SQR && cache[r - l][l])
		return cache[r - l][l];
	
	int mid = (l + r) >> 1; int ans = 2e9;
	
	int le[20], ri[20], lSize = 0, rSize = 0; 
	for (int i = mid; i >= l; i = nxtL[i]) le[lSize++] = i;
	reverse(le, le + lSize);
	for (int i = mid + 1; i <= r; i = nxtR[i]) ri[rSize++] = i;
	
	int id = rSize - 1, sumL = 0, sumR = 0;
	for (int i = 0; i < lSize; i++) {
		int pos = le[i];
		int k = max(nxtL[pos] + 1, l); // k -> pos
		if (l < k) {
			int B = nxtL[pos];
			int A = max(nxtL[B] + 1, l);
			sumL += (B - A + 1) * height[B];
		}
		int R = min(r + 1, nxtR[pos]);
		while (id >= 0 && ri[id] >= R) {
			if (id == rSize - 1) sumR += (r - ri[id] + 1) * height[ri[id]];
			else sumR += (ri[id + 1] - ri[id]) * height[ri[id]];
			--id;
		}
		int costL = sumL + dnc(k, pos) + height[pos] * (mid - pos);
		int costR = height[pos] * (R - 1 - mid) + sumR;
		ans = min(ans, costL + costR);
	}
	
	reverse(ri, ri + rSize);
	id = sumL = sumR = 0;
	for (int i = 0; i < rSize; i++) {
		int pos = ri[i];
		int k = min(nxtR[pos] - 1, r);
		if (k < r) {
			int A = nxtR[pos];
			int B = min(nxtR[A] - 1, r);
			sumR += (B - A + 1) * height[A];
		}
		int L = max(nxtL[pos], l - 1);
		while (id < lSize && le[id] <= L) {
			if (id == 0) sumL += (le[id] - l + 1) * height[le[id]];
			else sumL += (le[id] - le[id - 1]) * height[le[id]];
			++id;
		}
		int costL = sumL + height[pos] * (mid - L);
		int costR = (pos - 1 - mid) * height[pos] + dnc(pos, k) + sumR;
		ans = min(ans, costL + costR);
	}
	
	if (r - l <= SQR) cache[r - l][l] = ans;
	return ans;
}

ll pref[5005][5005];
vector <ll> minimum_costs(vector <int> H, vector <int> L, vector <int> R) {
	int n = H.size();
	if (*max_element(H.begin(), H.end()) <= 20) {
		height = H; 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]));
		return ans;
	}
	
	else {
		for (int i = 0; i < n; i++) {
			pref[i][i] = height[i];
			for (int j = i - 1, ma = height[i]; j >= 0; j--) {
				ma = max(ma, height[j]);
				pref[i][j] = ma;
			}
			for (int j = i + 1, ma = height[i]; j < n; j++) {
				ma = max(ma, height[j]);
				pref[i][j] = ma;
			}
			for (int j = 1; j < n; j++) pref[i][j] += pref[i][j - 1];
		}
		
		auto get = [&] (int u, int l, int r) {
			if (l == 0) return pref[u][r];
			return pref[u][r] - pref[u][l - 1];
		};
		
		vector <ll> ans;
		for (int i = 0; i < L.size(); i++) {
			ll res = 1e18;
			for (int u = L[i]; u <= R[i]; u++)
				res = min(res, get(u, L[i], R[i]));
			ans.emplace_back(res);
		}
		return ans;
	}
}

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