제출 #440202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440202		rainboy	모임들 (IOI18_meetings)	C++11	60 / 100	1473 ms	168964 KiB

meetings

#include "meetings.h"

using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;

const int N = 750000, N_ = 1 << 18, A = 20;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int qu[N]; long long pp[N], qq[N];

int ll_[N][A], rr_[N][A], xx[N], yy[N];

int eval_l(int l, int i) {
	int a, x;

	x = A * (i - l + 1);
	for (a = A - 1; a >= 0; a--)
		if (i >= ll_[i][a])
			x -= i - max(ll_[i][a], l) + 1;
	return x;
}

int eval_r(int r, int i) {
	int a, x;

	x = A * (r - i);
	for (a = A - 1; a >= 0; a--)
		if (i <= rr_[i][a])
			x -= min(rr_[i][a], r) - i;
	return x;
}

int sum[N_ * 2], pref[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	sum[i] = sum[l] + sum[r];
	pref[i] = min(pref[l], sum[l] + pref[r]);
}

void update(int i, int x) {
	i += n_;
	pref[i] = min(sum[i] = x, 0);
	while (i > 1)
		pul(i >>= 1);
}

int query(int l, int r) {
	int p, q, s;

	p = q = s = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			p = min(p, s + pref[l]), s += sum[l], l++;
		if ((r & 1) == 0)
			q = min(pref[r], sum[r] + q), r--;
	}
	return min(p, s + q);
}

vl minimum_costs(vi aa, vi ll, vi rr) {
	int n = aa.size(), q = ll.size(), h, cnt;
	vl ans(q);

	if (n <= 5000 && q <= 5000) {
		for (h = 0; h < q; h++) {
			int l = ll[h], r = rr[h], i;
			long long x;

			cnt = 0, x = 0;
			for (i = l; i <= r; i++) {
				x += aa[i];
				while (cnt && aa[qu[cnt - 1]] < aa[i]) {
					cnt--;
					x += (long long) (aa[i] - aa[qu[cnt]]) * (qu[cnt] - (cnt == 0 ? l - 1 : qu[cnt - 1]));
				}
				qu[cnt++] = i;
				pp[i] = x;
			}
			cnt = 0, x = 0;
			for (i = r; i >= l; i--) {
				x += aa[i];
				while (cnt && aa[qu[cnt - 1]] < aa[i]) {
					cnt--;
					x += (long long) (aa[i] - aa[qu[cnt]]) * ((cnt == 0 ? r + 1 : qu[cnt - 1]) - qu[cnt]);
				}
				qu[cnt++] = i;
				qq[i] = x;
			}
			ans[h] = INF;
			for (i = l; i <= r; i++)
				ans[h] = min(ans[h], pp[i] + qq[i] - aa[i]);
		}
	} else {
		int i, a;

		for (i = 0; i < n; i++)
			for (a = 0; a < A; a++)
				ll_[i][a] = aa[i] > a ? i + 1 : (i == 0 ? 0 : ll_[i - 1][a]);
		for (i = n - 1; i >= 0; i--)
			for (a = 0; a < A; a++)
				rr_[i][a] = aa[i] > a ? i - 1 : (i + 1 == n ? n - 1 : rr_[i + 1][a]);
		for (i = 1; i < n; i++)
			xx[i] = eval_l(0, i) - eval_l(0, i - 1), yy[i] = eval_r(n - 1, i) - eval_r(n - 1, i - 1);
		n_ = 1;
		while (n_ < n)
			n_ <<= 1;
		for (i = 1; i < n; i++)
			update(i, xx[i] + yy[i]);
		for (h = 0; h < q; h++) {
			int l = ll[h], r = rr[h];

			i = -1;
			for (a = 0; a < A; a++)
				if (i < rr_[l][a] + 1) {
					i = rr_[l][a] + 1;
					if (l < i && i <= r)
						update(i, eval_l(l, i) - eval_l(l, i - 1) + eval_r(r, i) - eval_r(r, i - 1));
				}
			i = n;
			for (a = 0; a < A; a++)
				if (i > ll_[r][a] - 1) {
					i = ll_[r][a] - 1;
					if (l < i + 1 && i + 1 <= r)
						update(i + 1, eval_l(l, i + 1) - eval_l(l, i) + eval_r(r, i + 1) - eval_r(r, i));
				}
			ans[h] = eval_l(l, l) + eval_r(r, l) + (l == r ? 0 : query(l + 1, r));
			i = -1;
			for (a = 0; a < A; a++)
				if (i < rr_[l][a] + 1) {
					i = rr_[l][a] + 1;
					if (l < i && i <= r)
						update(i, xx[i] + yy[i]);
				}
			i = n;
			for (a = 0; a < A; a++)
				if (i > ll_[r][a] - 1) {
					i = ll_[r][a] - 1;
					if (l < i + 1 && i + 1 <= r)
						update(i + 1, xx[i + 1] + yy[i + 1]);
				}
		}
	}
	return ans;
}

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