Submission #248469

#	Time	Username	Problem	Language	Result	Execution time	Memory
248469		kostia244	Meetings (IOI18_meetings)	C++17	0 / 100	26 ms	3576 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 90100;
int n, q, h[maxn], l[maxn], r[maxn];
vector<ll> ans;
ll tree[2*maxn];
void upd(int p, int v) {
	for(tree[p+=n] = v; p>>=1;) tree[p] = max(tree[p*2], tree[p*2+1]);
}
int get(int l, int r) {
	ll ans = -(1<<30);
	for(l += n, r += n+1; l < r; l>>=1, r>>=1) {
		if(l&1) ans = max(ans, tree[l++]);
		if(r&1) ans = max(ans, tree[--r]);
	}
	return ans;
}
int p[maxn], s[maxn];
ll solve(int l, int r) {
	int ans = (r-l+1)*2;
	if(r-p[r] < l) return r-l+1;
	int t = p[r];
	r -= p[r];
	t = max(t, get(l, r));
	return ans - t;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	q = L.size();
	n = H.size();
	for(int i = 0; i < n; i++) {
		h[i] = H[i];
		l[i] = L[i];
		r[i] = R[i];
	}
	ans.resize(q);
	memset(tree, -0x3f, sizeof tree);
	int t = 0;
	for(int i = 0; i < n; i++) {
		if(h[i] == 1) t++;
		else t = 0;
		p[i] = t;
	}
	t = 0;
	for(int i = n; i--;) {
		if(h[i] == 1) t++;
		else t = 0;
		upd(i, s[i] = t);
	}
	for(int i = 0; i < q; i++) ans[i] = solve(l[i], r[i]);
	return ans;
}

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