Submission #392802

#	Time	Username	Problem	Language	Result	Execution time	Memory
392802		JimmyZJX	Meetings (IOI18_meetings)	C++14	60 / 100	1243 ms	196500 KiB

meetings

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

int maxH[5003][5003];

LL dp[5003][5003];
int maxI[5003];

Vi h;

struct NodeInfo {
	int maxHeight;
	int sumLO[21], sumLI[21];
	int sumRI[21], sumRO[21];

	int GetMaxSum() {
		assert(sumLI[20] == sumRI[20]);
		return sumLI[20];
	}

	static NodeInfo empty() {
		NodeInfo info;
		info.maxHeight = 0;
		memset(info.sumLO, 0, sizeof(sumLO));
		memset(info.sumLI, 0, sizeof(sumLI));
		memset(info.sumRI, 0, sizeof(sumRI));
		memset(info.sumRO, 0, sizeof(sumRO));
		return info;
	}

	void initSingle(int h) {
		maxHeight = h;
		memset(sumLO, 0, sizeof(sumLO));
		memset(sumLI, 0, sizeof(sumLI));
		memset(sumRI, 0, sizeof(sumRI));
		memset(sumRO, 0, sizeof(sumRO));

		forR(i, 21) {
			sumLO[i] = sumRO[i] = min(20 - h, 20 - i);
			sumLI[i] = sumRI[i] = 20 - h;
		}
	}

	void update(const NodeInfo& left, const NodeInfo& right) {

		maxHeight = max(left.maxHeight, right.maxHeight);

		// LO
		int sumR = right.sumLO[left.maxHeight];
		{
			forR(i, 21) {
				sumLO[i] = left.sumLO[i] + right.sumLO[max(i, left.maxHeight)];
			}
		}
		// RO
		int sumL = left.sumRO[right.maxHeight];
		{
			forR(i, 21) {
				sumRO[i] = right.sumRO[i] + left.sumRO[max(i, right.maxHeight)];
			}
		}

		// LI
		{
			forR(i, 21) {
				sumLI[i] = left.sumLI[i] + sumR;
			}
			int MIDH = 0;
			forR(i, 21) {
				MIDH = max(MIDH, left.sumRI[i] + right.sumLO[i]);
			}

			int RO = 0;
			forR(i, left.maxHeight) {
				RO = max(RO, left.sumRO[i] + right.sumLI[i]);
			}

			for (int i = left.maxHeight; i < 21; i++) {
				RO = max(RO, left.sumRO[i] + right.sumLI[i]);
				sumLI[i] = max({ sumLI[i], MIDH, RO });
			}
		}

		// RI
		{
			forR(i, 21) {
				sumRI[i] = right.sumRI[i] + sumL;
			}
			int MIDH = 0;
			forR(i, 21) {
				MIDH = max({ MIDH, left.sumRO[i] + right.sumLI[i] });
			}

			int LO = 0;
			forR(i, right.maxHeight) {
				LO = max(LO, left.sumRI[i] + right.sumLO[i]);
			}

			for (int i = right.maxHeight; i < 21; i++) {
				LO = max(LO, left.sumRI[i] + right.sumLO[i]);
				sumRI[i] = max({ sumRI[i], MIDH, LO });
			}
		}
	}
};

struct SegNode {
	int l, r;
	SegNode* left, * right;
	NodeInfo info;

	inline int len() {
		return r - l + 1;
	}

	int calc(int l, int r) {
		auto info = maxRange(l, r);
		int cnt = r - l + 1;
		return cnt * 20 - info.GetMaxSum();
	}

	NodeInfo maxRange(int f, int t) { // [f, t]
		if (t < l || r < f) return NodeInfo::empty();
		if (f <= l && r <= t) return info;

		auto infoL = left->maxRange(f, t);
		auto infoR = right->maxRange(f, t);
		NodeInfo info;
		info.update(infoL, infoR);
		return info;
	}

	SegNode(int l, int r) {
		this->l = l; this->r = r;
		if (l == r) {
			info.initSingle(h[l]);
			left = right = nullptr;
		} else {
			int mid = (l + r) / 2;
			left = new SegNode(l, mid);
			right = new SegNode(mid + 1, r);
			info.update(left->info, right->info);
		}
	}
};

VL minimum_costs(Vi H, Vi L, Vi R) {
	int n = H.size(), q = L.size();

	h = H;
	int mH = 0;
	forR(i, n) { mH = max(mH, H[i]); }

	VL ans;

	if (mH <= 20) {
		SegNode* root = new SegNode(0, n - 1);

#ifdef TEST_LOCAL
		// check
		forR(i, n) for (int j = i; j < n; j++) {
			maxH[i][j] = H[i];
			for (int x = i + 1; x <= j; x++) {
				maxH[i][j] = max(maxH[i][j], H[x]);
			}
		}
		forR(i, n) for (int j = i; j < n; j++) {
			LL lowest = LLONG_MAX;
			for (int x = i; x <= j; x++) {
				LL cost = 0;
				for (int a = i; a <= x; a++) cost += maxH[a][x];
				for (int a = x + 1; a <= j; a++) cost += maxH[x][a];
				lowest = min(lowest, cost);
			}
			assert(root->calc(i, j) == lowest);
		}
#endif

		forR(i, q) {
			ans.push_back(root->calc(L[i], R[i]));
		}

		return ans;
	}

	if (n <= 5000) {

		memset(dp, 0, sizeof(dp));

		forR(i, n) {
			dp[i][i] = H[i];
			maxI[i] = i;
		}
		for (int d = 1; d < n; d++) {
			for (int i = 0; i + d < n; i++) {
				int j = i + d;
				if (H[j] > H[maxI[i]]) maxI[i] = j;

				int mi = maxI[i];
				if (mi == i) {
					dp[i][j] = H[i] + dp[i + 1][j];
				} else if (mi == j) {
					dp[i][j] = H[j] + dp[i][j - 1];
				} else {
					LL hMax = H[mi];
					dp[i][j] = min(dp[i][mi - 1] + hMax * (j - mi + 1),
						dp[mi + 1][j] + hMax * (mi - i + 1));
				}
			}
		}

#ifdef TEST_LOCAL
		// check
		forR(i, n) for (int j = i; j < n; j++) {
			maxH[i][j] = H[i];
			for (int x = i + 1; x <= j; x++) {
				maxH[i][j] = max(maxH[i][j], H[x]);
			}
		}
		forR(i, n) for (int j = i; j < n; j++) {
			bool hasEq = false;
			for (int x = i; x <= j; x++) {
				LL cost = 0;
				for (int a = i; a <= x; a++) cost += maxH[a][x];
				for (int a = x + 1; a <= j; a++) cost += maxH[x][a];
				assert(dp[i][j] <= cost);
				if (dp[i][j] == cost) hasEq = true;
			}
			assert(hasEq);
		}
#endif

		forR(i, q) {
			ans.push_back(dp[L[i]][R[i]]);
		}

		return ans;
	}

	return ans;
}

#ifdef TEST_LOCAL
int main() {
	Vi t;
	forR(s, 100) {
		t.clear();
		srand(s);
		forR(i, 50) {
			t.push_back(rand() % 20 + 1);
		}
		minimum_costs(t, Vi(), Vi());
	}

	return 0;
}
#endif

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