Submission #769045

#	Time	Username	Problem	Language	Result	Execution time	Memory
769045		SanguineChameleon	Meetings (IOI18_meetings)	C++17	19 / 100	492 ms	240936 KiB

meetings

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

const long long inf = 1e18L + 20;

struct node {
	int len, max_all, max_pref, max_suf;

	node(): len(0), max_all(0), max_pref(0), max_suf(0) {};

	node(int _len, int _max_all, int _max_pref, int _max_suf): len(_len), max_all(_max_all), max_pref(_max_pref), max_suf(_max_suf) {};
};

long long sum_l[5020][5020];
long long sum_r[5020][5020];
node tree[400020];
int H[100020];

node merge(node left, node right) {
	node res;
	res.len = left.len + right.len;
	res.max_pref = left.max_pref + (left.max_pref == left.len ? right.max_pref : 0);
	res.max_suf = right.max_suf + (right.max_suf == right.len ? left.max_suf : 0);
	res.max_all = max({left.max_all, right.max_all, res.max_pref, res.max_suf});
	return res;
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = node(1, (H[lt] == 1), (H[lt] == 1), (H[lt] == 1));
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}

node get(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return tree[id];
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		return merge(get(id * 2, lt, mt, ql, mt), get(id * 2 + 1, mt + 1, rt, mt + 1, qr));
	}
}

vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R) {
	int N = _H.size();
	for (int i = 0; i < N; i++) {
		H[i] = _H[i];
	}
	int Q = L.size();
	if (N <= 5000) {
		for (int i = 0; i < N; i++) {
			int mx = 0;
			long long sum = 0;
			for (int j = i; j >= 0; j--) {
				mx = max(mx, H[j]);
				sum += mx;
				sum_l[j][i] = sum;
			}
			mx = 0;
			sum = 0;
			for (int j = i; j < N; j++) {
				mx = max(mx, H[j]);
				sum += mx;
				sum_r[i][j] = sum;
			}
		}
		vector<long long> res(Q, inf);
		for (int i = 0; i < Q; i++) {
			for (int j = L[i]; j <= R[i]; j++) {
				res[i] = min(res[i], sum_l[L[i]][j] + sum_r[j][R[i]] - H[j]);
			}
		}
		return res;
	}
	else {
		build(1, 0, N - 1);
		vector<long long> res(Q);
		for (int i = 0; i < Q; i++) {
			res[i] = (R[i] - L[i] + 1) * 2 - get(1, 0, N - 1, L[i], R[i]).max_all;
		}
		return res;
	}
	return vector<long long>();
}

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