Submission #556777

#	Time	Username	Problem	Language	Result	Execution time	Memory
556777		lunchbox	Distributing Candies (IOI21_candies)	C++17	100 / 100	314 ms	29252 KiB

candies

/*
https://oj.uz/problem/view/IOI21_candies
Distributing Candies
*/
#include <bits/stdc++.h>
using namespace std;

#define N	200000
#define Q	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N)) */

long long sum[N_ * 2], mn[N_ * 2], mx[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1 | 0, r = i << 1 | 1;

	sum[i] = sum[l] + sum[r];
	mn[i] = min(mn[r], mn[l] + sum[r]);
	mx[i] = max(mx[r], mx[l] + sum[r]);
}

void update(int i, int x) {
	i |= n_;
	sum[i] = x;
	mn[i] = min(x, 0);
	mx[i] = max(x, 0);
	while (i > 1)
		pul(i >>= 1);
}

int query(int c) {
	long long s = 0, mn_ = 0, mx_ = 0;
	int i = 1;

	if (mx[1] - mn[1] <= c)
		return mx[1];
	while (i < n_)
		if (max(mx_, mx[i << 1 | 1] + s) - min(mn_, mn[i << 1 | 1] + s) <= c) {
			i = i << 1 | 0;
			mn_ = min(mn_, mn[i ^ 1] + s);
			mx_ = max(mx_, mx[i ^ 1] + s);
			s += sum[i ^ 1];
		} else
			i = i << 1 | 1;
	return min(max(sum[i] + s, mx_), c + mn_);
}

using vi = vector<int>;

vi distribute_candies(vi aa, vi ll, vi rr, vi vv) {
	vector<array<int, 3>> ee;
	int n, q, e;
	vi ans;

	n = aa.size(), q = ll.size();
	for (int h = 0; h < q; h++) {
		int l = ll[h], r = rr[h], v = vv[h];

		ee.push_back({l, h, v});
		ee.push_back({r + 1, h, 0});
	}
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	e = 0, sort(ee.begin(), ee.end());
	for (int i = 0; i < n; i++) {
		while (e < q * 2 && ee[e][0] <= i) {
			update(ee[e][1], ee[e][2]);
			e++;
		}
		ans.push_back(query(aa[i]));
	}
	return ans;
}

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