Submission #440047

#	Time	Username	Problem	Language	Result	Execution time	Memory
440047		rainboy	Meetings (IOI18_meetings)	C++11	19 / 100	5565 ms	7180 KiB

meetings

#include "meetings.h"

using namespace std;

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

const int N = 750000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

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

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

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

	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]);
	}
	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'vl minimum_costs(vi, vi, vi)':
meetings.cpp:16:6: warning: unused variable 'n' [-Wunused-variable]
   16 |  int n = aa.size(), q = ll.size(), h, cnt;
      |      ^

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