Submission #300011

#	Time	Username	Problem	Language	Result	Execution time	Memory
300011		square1001	Meetings (IOI18_meetings)	C++14	41 / 100	3773 ms	23520 KiB

meetings

#include "meetings.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	int N = H.size(), Q = L.size();
	int Z = *max_element(H.begin(), H.end());
	vector<vector<int> > splitter(Z + 1);
	for(int i = 0; i <= Z; ++i) {
		splitter[i].push_back(0);
		for(int j = 0; j < N; ++j) {
			if(H[j] > i) {
				splitter[i].push_back(j + 1);
			}
		}
		splitter[i].push_back(N + 1);
	}
	vector<int> spsize(Z + 1);
	for(int i = 0; i <= Z; ++i) {
		spsize[i] = int(splitter[i].size()) - 1;
	}
	vector<vector<long long> > dp(Z + 1);
	dp[0] = vector<long long>(spsize[0], 1);
	for(int i = 1; i <= Z; ++i) {
		dp[i].resize(spsize[i]);
		for(int j = 0; j < spsize[i]; ++j) {
			int pl = lower_bound(splitter[i - 1].begin(), splitter[i - 1].end(), splitter[i][j]) - splitter[i - 1].begin();
			int pr = lower_bound(splitter[i - 1].begin(), splitter[i - 1].end(), splitter[i][j + 1]) - splitter[i - 1].begin();
			int mx = *max_element(dp[i - 1].begin() + pl, dp[i - 1].begin() + pr);
			dp[i][j] = mx + (splitter[i][j + 1] - splitter[i][j]);
		}
	}
	vector<long long> res(Q);
	for(int i = 0; i < Q; ++i) {
		// part #0. precalc
		vector<int> pl(Z + 1), pr(Z + 1);
		for(int j = 0; j <= Z; ++j) {
			pl[j] = splitter[j][lower_bound(splitter[j].begin(), splitter[j].end(), L[i] + 1) - splitter[j].begin()];
			pr[j] = splitter[j][lower_bound(splitter[j].begin(), splitter[j].end(), R[i] + 2) - splitter[j].begin() - 1];
		}
		int height = 0;
		for(int j = 0; j <= Z; ++j) {
			if(pl[j] <= pr[j]) {
				height = j;
			}
		}
		long long ans = 0;
		// part #1. midvaue
		int sl = lower_bound(splitter[height].begin(), splitter[height].end(), L[i] + 1) - splitter[height].begin();
		int sr = lower_bound(splitter[height].begin(), splitter[height].end(), R[i] + 2) - splitter[height].begin();
		for(int j = sl; j < sr - 1; ++j) {
			ans = max(ans, dp[height][j]);
		}
		// part #2. leftvalue
		long long suml = 0;
		for(int j = height - 1; j >= 0; --j) {
			suml += pl[j + 1] - L[i];
			int tl = lower_bound(splitter[j].begin(), splitter[j].end(), pl[j]) - splitter[j].begin();
			int tr = lower_bound(splitter[j].begin(), splitter[j].end(), pl[j + 1]) - splitter[j].begin();
			for(int k = tl; k < tr; ++k) {
				ans = max(ans, suml + dp[j][k]);
			}
		}
		suml += pl[0] - L[i];
		ans = max(ans, suml);
		// part #3. rightvalue
		long long sumr = 0;
		for(int j = height - 1; j >= 0; --j) {
			sumr += (R[i] + 2) - pr[j + 1];
			int tl = lower_bound(splitter[j].begin(), splitter[j].end(), pr[j + 1]) - splitter[j].begin();
			int tr = lower_bound(splitter[j].begin(), splitter[j].end(), pr[j]) - splitter[j].begin();
			for(int k = tl; k < tr; ++k) {
				ans = max(ans, sumr + dp[j][k]);
			}
		}
		sumr += (R[i] + 2) - pr[0];
		ans = max(ans, sumr);
		res[i] = 1LL * (height + 1) * (R[i] - L[i] + 2) - ans;
	}
	return res;
}

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