Submission #412137

#	Time	Username	Problem	Language	Result	Execution time	Memory
412137		Mlxa	Meetings (IOI18_meetings)	C++14	17 / 100	76 ms	7236 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "meetings.h"

namespace my {
const int N = 1 << 17;
vector<pair<int, int>> segs;
int f[N], b[N];
int tree[2 * N];
int query(int l, int r) {
	int res = 0;
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			res = max(res, tree[l++]);
		}
		if (r % 2 == 0) {
			res = max(res, tree[r--]);
		}
	}
	return res;
}
}

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	using namespace my;
	int n = (int)h.size();
	int q = (int)l.size();
	vector<ll> c(q);
	for (int i = n - 1; i >= 0; --i) {
		f[i] = h[i] == 1 ? f[i + 1] + 1 : 0;
	}
	b[0] = h[0] == 1 ? 1 : 0;
	for (int i = 1; i < n; ++i) {
		b[i] = h[i] == 1 ? b[i - 1] + 1 : 0;
	}
	copy_n(f, N, tree + N);
	for (int i = N - 1; i > 0; --i) {
		tree[i] = max(tree[i + i], tree[i + i + 1]);
	}
	for (int it = 0; it < q; ++it) {
		int lef = l[it], rig = r[it], len = rig - lef + 1;
		int mx = min(len, max(f[lef], b[rig]));
		lef += f[lef];
		rig -= b[rig];
		mx = max(mx, query(lef, rig));
		c[it] = 2 * len - mx;
	}
	return c;
}

#ifdef LC
#include "grader.cpp"
#endif

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