oj.uz

Submission #557928

# Submission time Handle Problem Language Result Execution time Memory
557928 2022-05-06T10:10:43 Z surgutti Distributing Candies (IOI21_candies) C++17
100 / 100
 318 ms 31812 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 25704 KB Output is correct
2 Correct 271 ms 26076 KB Output is correct
3 Correct 318 ms 25980 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 188 ms 26568 KB Output is correct
3 Correct 67 ms 6152 KB Output is correct
4 Correct 277 ms 31036 KB Output is correct
5 Correct 290 ms 31432 KB Output is correct
6 Correct 277 ms 31812 KB Output is correct
7 Correct 275 ms 31124 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 104 ms 26272 KB Output is correct
4 Correct 55 ms 4200 KB Output is correct
5 Correct 165 ms 28604 KB Output is correct
6 Correct 157 ms 29328 KB Output is correct
7 Correct 167 ms 29884 KB Output is correct
8 Correct 164 ms 28488 KB Output is correct
9 Correct 170 ms 30024 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 318 ms 25704 KB Output is correct
7 Correct 271 ms 26076 KB Output is correct
8 Correct 318 ms 25980 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 188 ms 26568 KB Output is correct
11 Correct 67 ms 6152 KB Output is correct
12 Correct 277 ms 31036 KB Output is correct
13 Correct 290 ms 31432 KB Output is correct
14 Correct 277 ms 31812 KB Output is correct
15 Correct 275 ms 31124 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 104 ms 26272 KB Output is correct
19 Correct 55 ms 4200 KB Output is correct
20 Correct 165 ms 28604 KB Output is correct
21 Correct 157 ms 29328 KB Output is correct
22 Correct 167 ms 29884 KB Output is correct
23 Correct 164 ms 28488 KB Output is correct
24 Correct 170 ms 30024 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 68 ms 4012 KB Output is correct
27 Correct 199 ms 26236 KB Output is correct
28 Correct 247 ms 29640 KB Output is correct
29 Correct 294 ms 30020 KB Output is correct
30 Correct 285 ms 30240 KB Output is correct
31 Correct 295 ms 30524 KB Output is correct
32 Correct 292 ms 30652 KB Output is correct