Submission #838312

#	Time	Username	Problem	Language	Result	Execution time	Memory
838312		happypotato	Distributing Candies (IOI21_candies)	C++17	100 / 100	348 ms	41728 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

const int mxN = 2e5 + 1;
struct info {
	int net; // net change
	int mini, maxi;
	info(): net(0), mini(1e18), maxi(-1e18) {};
	info(int val): net(val), mini(val), maxi(val) {};
};
info merge(info &lhs, info &rhs) {
	info res;
	res.net = lhs.net + rhs.net;
	res.mini = min(lhs.mini, lhs.net + rhs.mini);
	res.maxi = max(lhs.maxi, lhs.net + rhs.maxi);
	return res;
}
info EMPTY = info();
info ZERO = info(0);
info seg[4 * mxN];
int lazy[4 * mxN];
int n, q;
void build(int l = 0, int r = q, int idx = 1) {
	if (l == r) {
		if (l == 0) seg[idx] = info(0);
		else seg[idx] = info();
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 0, int r = q, int idx = 1) {
	if (l == r) {
		if (val == 0) seg[idx] = info();
		else seg[idx] = info(val);
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) update(pos, val, l, mid, (idx << 1));
	else update(pos, val, mid + 1, r, (idx << 1) | 1);
	seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
// range find net min/max
pii query1(int tl, int tr, int l = 0, int r = q, int idx = 1, int buff = 0) {
	if (tl > tr) return {0, 0};
	if (tl <= l && r <= tr) return {buff + seg[idx].mini, buff + seg[idx].maxi};
	int mid = (l + r) >> 1;
	pii res = {1e18, -1e18}, ret;
	if (tl <= mid) {
		ret = query1(tl, tr, l, mid, (idx << 1), buff);
		res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
	}
	if (tr > mid) {
		ret = query1(tl, tr, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
		res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
	}
	return res;
}
// find largest pos s.t. max(upd[pos..n]) - min(upd[pos..n]) > (tar = c[i])
int query2(int tar, pii range, int l = 0, int r = q, int idx = 1, int buff = 0) {
	if (max(range.ss, buff + seg[idx].maxi) - min(range.ff, buff + seg[idx].mini) <= tar) {
		return -1;
	}
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int rmini = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].mini;
	int rmaxi = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].maxi;
	if (max(range.ss, rmaxi) - min(range.ff, rmini) <= tar) {
		range.ss = max(range.ss, rmaxi);
		range.ff = min(range.ff, rmini);
		return query2(tar, range, l, mid, (idx << 1), buff);
	} else {
		return query2(tar, range, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
	}
	return -1;
}

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l,
                                   vector<int32_t> r, vector<int32_t> v) {
	
	n = c.size(); q = v.size();
	build();
	vector<pii> upd[n + 2];
	for (int i = 0; i < q; i++) {
		l[i]++; r[i]++;
		upd[l[i]].pb({i + 1, v[i]});
		upd[r[i] + 1].pb({i + 1, 0});
	}

	vector<int32_t> ans;
	for (int i = 1; i <= n; i++) {
		for (pii &cur : upd[i]) {
			update(cur.ff, cur.ss);
		}
		int tot = seg[1].net;
		int crit = query2(c[i - 1], {tot, tot});
		pii range;
		if (crit == -1) {
			range = query1(0, q);
			ans.pb(tot - range.ff);
			continue;
		}
		int prev = query1(crit, crit).ff;
		range = query1(crit + 1, q);
		if (prev < range.ff) {
			range.ff = range.ss - c[i - 1];
			ans.pb(tot - range.ff);
		} else {
			range.ss = range.ff + c[i - 1];
			ans.pb(c[i - 1] - (range.ss - tot));
		}
	}
	return ans;
}

#undef int

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33