Submission #557928

#	Time	Username	Problem	Language	Result	Execution time	Memory
557928		surgutti	Distributing Candies (IOI21_candies)	C++17	100 / 100	318 ms	31812 KiB

candies

#include <bits/stdc++.h>

using namespace std;

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
	int n = (int) c.size();
	int q = (int) l.size();

	int tree_size = 1;
	while (tree_size < q) {
		tree_size <<= 1;
	}

	vector<long long> sumi(tree_size << 1);
	vector<long long> mini(tree_size << 1);
	vector<long long> maxi(tree_size << 1);

	auto update = [&](int pos, int val) {
		pos += tree_size;
		sumi[pos] = val;
		maxi[pos] = max(0, val);
		mini[pos] = min(0, val);
		for (; pos >>= 1; ) {
			sumi[pos] = sumi[pos << 1 | 0] + sumi[pos << 1 | 1];
			mini[pos] = min(mini[pos << 1 | 1], sumi[pos << 1 | 1] + mini[pos << 1 | 0]);
			maxi[pos] = max(maxi[pos << 1 | 1], sumi[pos << 1 | 1] + maxi[pos << 1 | 0]);
		}
	};

	auto query = [&](int C) {
		if (maxi[1] - mini[1] <= C) {
			return maxi[1];
		}

		int u = 1;
		
		long long my_sum = 0, my_min = 0, my_max = 0;

		while (u < tree_size) {
			if (max(my_max, my_sum + maxi[u << 1 | 1]) -
				min(my_min, my_sum + mini[u << 1 | 1]) <= C) {
			
				my_max = max(my_max, my_sum + maxi[u << 1 | 1]);
				my_min = min(my_min, my_sum + mini[u << 1 | 1]);
				my_sum = my_sum + sumi[u << 1 | 1];

				u = u << 1 | 0;
			}
			else {
				u = u << 1 | 1;
			}
		}
		
		return min(max(sumi[u] + my_sum, my_max), C + my_min);
	};

	struct Event {
		int i, p, v;
	};

	vector<Event> events;

	for (int i = 0; i < q; i++) {
		events.push_back(Event{l[i] + 0, i, v[i]});
		events.push_back(Event{r[i] + 1, i, 0});
	}

	sort(events.begin(), events.end(),
		[](const Event &a, const Event &b) {
			return a.i < b.i;
		}
	);

	vector<int> ans(n);

	int cur_event = 0;
	for (int i = 0; i < n; i++) {
		while (cur_event < (int) events.size() && events[cur_event].i <= i) {
			update(events[cur_event].p, events[cur_event].v);
			cur_event++;
		}
		
		ans[i] = query(c[i]);
	}

	return ans;
}

#ifdef LOCAL

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int a, int b) {
	return uniform_int_distribution<int>(a, b)(rng);
}

int main() {

	auto ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});

	for (int i : ans)
		cout << i << ' ';
	cout << '\n';
}

#endif // LOCAL

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