Submission #440600

#	Time	Username	Problem	Language	Result	Execution time	Memory
440600		rainboy	Meetings (IOI18_meetings)	C++11	100 / 100	3026 ms	152232 KiB

meetings

#include "meetings.h"

using namespace std;

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

const int N = 750000, H = 19;

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 aa[N], qu[N], pp[N], qq[N], n; long long dp[N], dq[N];
int ii[H + 1][N], hh[N + 1];

void build(int n) {
	int h, i, j;

	for (i = 0; i < n; i++)
		ii[0][i] = i;
	for (h = 1; h <= H; h++)
		for (i = 0; i < n; i++)
			ii[h][i] = ii[h - 1][(j = i + (1 << h - 1)) >= n || aa[ii[h - 1][i]] >= aa[ii[h - 1][j]] ? i : j];
	for (i = 1, h = 0; i <= n; i++) {
		while (1 << h + 1 <= i)
			h++;
		hh[i] = h;
	}
}

int get(int l, int r) {
	int h = hh[r - l + 1];

	return ii[h][aa[ii[h][l]] >= aa[ii[h][r - (1 << h) + 1]] ? l : r - (1 << h) + 1];
}

long long A(int i, int l) {
	int j = get(l, i);

	return dp[i] - ((pp[j] == -1 ? 0 : dp[pp[j]]) + (long long) aa[j] * (l - pp[j] - 1)) + dq[i] - aa[i];
}

long long B(int i, int r) {
	int j = get(i, r);

	return dq[i] - ((qq[j] == n ? 0 : dq[qq[j]]) + (long long) aa[j] * (qq[j] - r - 1)) + dp[i] - aa[i];
}

int L(int i, int j) {
	int lower = -1, upper = j + 1;

	while (upper - lower > 1) {
		int l = (lower + upper) / 2;

		if (A(i, l) >= A(j, l))
			lower = l;
		else
			upper = l;
	}
	return lower;
}

int R(int i, int j) {
	int lower = j - 1, upper = n;

	while (upper - lower > 1) {
		int r = (lower + upper) / 2;

		if (B(i, r) >= B(j, r))
			upper = r;
		else
			lower = r;
	}
	return upper;
}

int pp_[N], pp1[N], prank[N], qq_[N], qq1[N], qrank[N], ll_[N], rr_[N];

long long A_(int i, int l) {
	return ll_[i] < l ? A(i, l) : A_(ll_[pp1[i]] >= l ? pp1[i] : pp_[i], l);
}

long long B_(int i, int r) {
	return rr_[i] > r ? B(i, r) : B_(rr_[qq1[i]] <= r ? qq1[i] : qq_[i], r);
}

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

	n = aa_.size();
	cnt = 0;
	for (i = 0; i < n; i++) {
		aa[i] = aa_[i];
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			qq[qu[--cnt]] = i;
		pp[i] = cnt == 0 ? -1 : qu[cnt - 1];
		qu[cnt++] = i;
	}
	while (cnt--)
		qq[qu[cnt]] = n;
	for (i = 0; i < n; i++)
		dp[i] = (pp[i] == -1 ? 0 : dp[pp[i]]) + (long long) aa[i] * (i - pp[i]);
	for (i = n - 1; i >= 0; i--)
		dq[i] = (qq[i] == n ? 0 : dq[qq[i]]) + (long long) aa[i] * (qq[i] - i);
	build(n);
	cnt = 0, pp_[0] = ll_[0] = -1, pp1[0] = -1, prank[0] = -1, qu[cnt++] = 0;
	for (i = 1; i < n; i++) {
		while (cnt >= 2 && A(qu[cnt - 1], ll_[qu[cnt - 1]] + 1) > A(i, ll_[qu[cnt - 1]] + 1))
			cnt--;
		pp_[i] = qu[cnt - 1], ll_[i] = L(i, pp_[i]), qu[cnt++] = i;
		if (pp1[pp_[i]] != -1 && prank[pp1[pp_[i]]] == prank[pp_[i]])
			pp1[i] = pp1[pp1[pp_[i]]], prank[i] = prank[pp_[i]] + 1;
		else
			pp1[i] = pp_[i], prank[i] = 0;
	}
	cnt = 0, qq1[n - 1] = qq_[n - 1] = rr_[n - 1] = n, qq1[n - 1] = n, qrank[n - 1] = -1, qu[cnt++] = n - 1;
	for (i = n - 2; i >= 0; i--) {
		while (cnt >= 2 && B(qu[cnt - 1], rr_[qu[cnt - 1]] - 1) > B(i, rr_[qu[cnt - 1]] - 1))
			cnt--;
		qq_[i] = qu[cnt - 1], rr_[i] = R(i, qq_[i]), qu[cnt++] = i;
		if (qq1[qq_[i]] != n && qrank[qq1[qq_[i]]] == qrank[qq_[i]])
			qq1[i] = qq1[qq1[qq_[i]]], qrank[i] = qrank[qq_[i]] + 1;
		else
			qq1[i] = qq_[i], qrank[i] = 0;
	}
	for (h = 0; h < q; h++) {
		int l = ll[h], r = rr[h], m = get(l, r);

		ans[h] = (long long) aa[m] * (r - l + 1);
		if (m > l)
			ans[h] = min(ans[h], A_(m - 1, l) - ((qq[m] == n ? 0 : dq[qq[m]]) + (long long) aa[m] * (qq[m] - r - 1)));
		if (m < r)
			ans[h] = min(ans[h], B_(m + 1, r) - ((pp[m] == -1 ? 0 : dp[pp[m]]) + (long long) aa[m] * (l - pp[m] - 1)));
	}
	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'void build(int)':
meetings.cpp:23:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |    ii[h][i] = ii[h - 1][(j = i + (1 << h - 1)) >= n || aa[ii[h - 1][i]] >= aa[ii[h - 1][j]] ? i : j];
      |                                        ~~^~~
meetings.cpp:25:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |   while (1 << h + 1 <= i)
      |               ~~^~~

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