oj.uz

Submission #435101

# Submission time Handle Problem Language Result Execution time Memory
435101 2021-06-23T02:45:22 Z Elegia Distributing Candies (IOI21_candies) C++17
100 / 100
 587 ms 32964 KB 
#include "candies.h"

#include <algorithm>
#include <iostream>
#include <vector>

using ll = long long;

const int INF = int(1e9) + 1;
const int N = 1 << 18, SZ = N << 1;

ll sum[SZ], minv[SZ], maxv[SZ];

void change(int o, int l, int r, int k, int v) {
	if (l == r) {
		sum[o] = v;
		minv[o] = std::min(v, 0);
		maxv[o] = std::max(v, 0);
		return;
	}
	int mid = (l + r) / 2;
	if (k <= mid) change(o << 1, l, mid, k, v);
	else change(o << 1 | 1, mid + 1, r, k, v);

	sum[o] = sum[o << 1] + sum[o << 1 | 1];
	minv[o] = std::min(minv[o << 1], sum[o << 1] + minv[o << 1 | 1]);
	maxv[o] = std::max(maxv[o << 1], sum[o << 1] + maxv[o << 1 | 1]);
}

std::vector<std::pair<int, int>> modify[N];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
	int n = c.size(), m = l.size();
	for (int i = 0; i != m; ++i) {
		modify[l[i]].emplace_back(i + 2, v[i]);
		modify[r[i] + 1].emplace_back(i + 2, 0);
	}
	m += 1;
	change(1, 0, m, 0, INF);
	change(1, 0, m, 1, -INF);

	std::vector<int> ans(n);
	for (int i = 0; i != n; ++i) {
		for (const auto& [k, v] : modify[i])
			change(1, 0, m, k, v);
		ll vl = sum[1], vr = sum[1], s = 0;
		int o = 1, l = 0, r = m;
		while (l != r) {
			int mid = (l + r) / 2;
			ll nl = std::min(vl, s + sum[o << 1] + minv[o << 1 | 1]),
			   nr = std::max(vr, s + sum[o << 1] + maxv[o << 1 | 1]);
			if (nr - nl > c[i]) {
				s += sum[o << 1];
				o = o << 1 | 1;
				l = mid + 1;
			} else {
				vl = nl;
				vr = nr;
				o = o << 1;
				r = mid;
			}
		}
		if (s <= vl)
			ans[i] = c[i] - (vr - sum[1]);
		else
			ans[i] = sum[1] - vl;
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 6 ms 6680 KB Output is correct
4 Correct 7 ms 6604 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 32752 KB Output is correct
2 Correct 554 ms 32876 KB Output is correct
3 Correct 508 ms 32884 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 300 ms 27888 KB Output is correct
3 Correct 77 ms 10144 KB Output is correct
4 Correct 503 ms 32832 KB Output is correct
5 Correct 536 ms 32928 KB Output is correct
6 Correct 485 ms 32960 KB Output is correct
7 Correct 479 ms 32832 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6348 KB Output is correct
2 Correct 5 ms 6376 KB Output is correct
3 Correct 140 ms 26620 KB Output is correct
4 Correct 82 ms 9020 KB Output is correct
5 Correct 196 ms 28832 KB Output is correct
6 Correct 211 ms 28844 KB Output is correct
7 Correct 205 ms 28956 KB Output is correct
8 Correct 201 ms 28956 KB Output is correct
9 Correct 200 ms 28952 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6348 KB Output is correct
2 Correct 5 ms 6348 KB Output is correct
3 Correct 6 ms 6680 KB Output is correct
4 Correct 7 ms 6604 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct
6 Correct 587 ms 32752 KB Output is correct
7 Correct 554 ms 32876 KB Output is correct
8 Correct 508 ms 32884 KB Output is correct
9 Correct 5 ms 6476 KB Output is correct
10 Correct 300 ms 27888 KB Output is correct
11 Correct 77 ms 10144 KB Output is correct
12 Correct 503 ms 32832 KB Output is correct
13 Correct 536 ms 32928 KB Output is correct
14 Correct 485 ms 32960 KB Output is correct
15 Correct 479 ms 32832 KB Output is correct
16 Correct 5 ms 6348 KB Output is correct
17 Correct 5 ms 6376 KB Output is correct
18 Correct 140 ms 26620 KB Output is correct
19 Correct 82 ms 9020 KB Output is correct
20 Correct 196 ms 28832 KB Output is correct
21 Correct 211 ms 28844 KB Output is correct
22 Correct 205 ms 28956 KB Output is correct
23 Correct 201 ms 28956 KB Output is correct
24 Correct 200 ms 28952 KB Output is correct
25 Correct 5 ms 6476 KB Output is correct
26 Correct 77 ms 9028 KB Output is correct
27 Correct 278 ms 27844 KB Output is correct
28 Correct 482 ms 32848 KB Output is correct
29 Correct 511 ms 32768 KB Output is correct
30 Correct 483 ms 32716 KB Output is correct
31 Correct 512 ms 32964 KB Output is correct
32 Correct 532 ms 32928 KB Output is correct