Submission #794039

#	Time	Username	Problem	Language	Result	Execution time	Memory
794039		Sohsoh84	Meetings (IOI18_meetings)	C++17	17 / 100	71 ms	8360 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define sep			' '
#define debug(x)		cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

ll FL[MAXN], FR[MAXN], n;

namespace segment {
	int sg[MAXN];

	void update(int ind, int val, int l = 0, int r = n - 1, int v = 1) {
		if (l == r) sg[v] = val;
		else {
			int mid = (l + r) >> 1;
			if (ind <= mid) update(ind, val, l, mid, v << 1);
			else update(ind, val, mid + 1, r, v << 1 | 1);

			sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
		}
	}
	
	int query(int ql, int qr, int l = 0, int r = n - 1, int v = 1) {
		if (ql > r || qr < l) return 0;
		if (ql <= l && qr >= r) return sg[v];

		int mid = (l + r) >> 1;
		return max(query(ql, qr, l, mid, v << 1),
				query(ql, qr, mid + 1, r, v << 1 | 1));
	}
}

vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	int Q = L.size();	
	n = H.size();
	vector<ll> ans(Q);
	
	for (int i = 0; i < n; i++) {
		FL[i] = (H[i] == 1);
		if (i && FL[i]) FL[i] += FL[i - 1];

		segment::update(i, FL[i]);
	}

	for (int i = n - 1; i >= 0; i--) {
		FR[i] = (H[i] == 1);
		if (FR[i]) FR[i] += FR[i + 1];
	}

	for (int i = 0; i < Q; i++) {
		int l = L[i], r = R[i];
		ans[i] = 2 * (r - l + 1);

		if (r - FL[r] < l) {
			ans[i] = (r - l + 1);
			continue;
		}

		int tans = max(FL[r], FR[l]);
	
		r -= FL[r];
		l += FR[l];

		tans = max(tans, segment::query(l, r));
		ans[i] -= tans;
	}

	return ans;
}

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