Submission #300016

#	Time	Username	Problem	Language	Result	Execution time	Memory
300016		square1001	Meetings (IOI18_meetings)	C++14	60 / 100	3872 ms	36892 KiB

meetings

#include "meetings.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
long long calc(vector<int> H) {
	int N = H.size();
	vector<pair<int, int> > stairs;
	stairs.push_back(make_pair(inf, -1));
	long long sum = 0;
	vector<long long> sl(N);
	for(int i = 0; i < N; ++i) {
		while(stairs.back().first <= H[i]) {
			pair<int, int> pa = stairs[stairs.size() - 1];
			pair<int, int> pb = stairs[stairs.size() - 2];
			sum -= 1LL * pa.first * (pa.second - pb.second);
			stairs.pop_back();
		}
		sum += 1LL * H[i] * (i - stairs.back().second);
		stairs.push_back(make_pair(H[i], i));
		sl[i] = sum;
	}
	stairs.clear();
	stairs.push_back(make_pair(inf, N));
	sum = 0;
	vector<long long> sr(N);
	for(int i = N - 1; i >= 0; --i) {
		while(stairs.back().first <= H[i]) {
			pair<int, int> pa = stairs[stairs.size() - 1];
			pair<int, int> pb = stairs[stairs.size() - 2];
			sum -= 1LL * pa.first * (pb.second - pa.second);
			stairs.pop_back();
		}
		sum += 1LL * H[i] * (stairs.back().second - i);
		stairs.push_back(make_pair(H[i], i));
		sr[i] = sum;
	}
	long long ans = 1LL << 62;
	for(int i = 0; i < N; ++i) {
		ans = min(ans, sl[i] + sr[i] - H[i]);
	}
	return ans;
}
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();
	if(N <= 5000 && Q <= 5000) {
		vector<long long> res(Q);
		for(int i = 0; i < Q; ++i) {
			res[i] = calc(vector<int>(H.begin() + L[i], H.begin() + R[i] + 1));
		}
		return res;
	}
	else {
		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;
	}
	return vector<long long>();
}

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