Submission #392762

#	Time	Username	Problem	Language	Result	Execution time	Memory
392762		JimmyZJX	Meetings (IOI18_meetings)	C++14	36 / 100	443 ms	425852 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 {
	bool isAll1;
	int c1L, c1R, maxC1;

	void update(const NodeInfo& left, const NodeInfo& right) {
		// left
		c1L = left.c1L;
		if (left.isAll1) {
			c1L += right.c1L;
		}

		// right
		c1R = right.c1R;
		if (right.isAll1) {
			c1R += left.c1R;
		}

		isAll1 = left.isAll1 && right.isAll1;
		maxC1 = max({ c1L, c1R, left.maxC1, right.maxC1, left.c1R + right.c1L });
	}
};

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

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

	NodeInfo maxRange(int f, int t) { // [f, t]
		if (t < l || r < f) return NodeInfo{ true, 0, 0, 0 };
		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) {
			if (h[l] == 1) {
				info.isAll1 = true;
				info.c1L = info.c1R = info.maxC1 = 1;
			} else {
				info.isAll1 = false;
				info.c1L = info.c1R = info.maxC1 = 0;
			}
			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 == 2) {
		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++) {

			auto info = root->maxRange(i, j);
			int cnt = j - i + 1;
			int Qij = cnt * 2 - info.maxC1;

			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(Qij <= cost);
				if (Qij == cost) hasEq = true;
			}
			assert(hasEq);
		}
#endif

		forR(i, q) {
			auto info = root->maxRange(L[i], R[i]);
			int cnt = R[i] - L[i] + 1;
			ans.push_back(cnt * 2 - info.maxC1);
		}

		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;
	}
}

#ifdef TEST_LOCAL
int main() {
	minimum_costs(Vi{ 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1 }, Vi{ 0, 1 }, Vi{ 1,2 });

	return 0;
}
#endif

Compilation message (stderr)

meetings.cpp: In function 'VL minimum_costs(Vi, Vi, Vi)':
meetings.cpp:196:1: warning: control reaches end of non-void function [-Wreturn-type]
  196 | }
      | ^

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