제출 #440556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440556		rainboy	Meetings (IOI18_meetings)	C++11	19 / 100	5529 ms	14764 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];
}

vl minimum_costs(vi aa_, vi ll, vi rr) {
	int q = ll.size(), h, i, j, 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);
	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);
		for (i = l; i < m; i++) {
			j = get(l, i);
			ans[h] = min(ans[h], dp[i] - ((pp[j] == -1 ? 0 : dp[pp[j]]) + (long long) aa[j] * (l - pp[j] - 1)) + dq[i] - ((qq[m] == n ? 0 : dq[qq[m]]) + (long long) aa[m] * (qq[m] - r - 1)) - aa[i]);
		}
		for (i = m + 1; i <= r; i++) {
			j = get(i, r);
			ans[h] = min(ans[h], dp[i] - ((pp[m] == -1 ? 0 : dp[pp[m]]) + (long long) aa[m] * (l - pp[m] - 1)) + dq[i] - ((qq[j] == n ? 0 : dq[qq[j]]) + (long long) aa[j] * (qq[j] - r - 1)) - aa[i]);
		}
	}
	return ans;
}

컴파일 시 표준 에러 (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: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40