oj.uz

Submission #557921

# Submission time Handle Problem Language Result Execution time Memory
557921 2022-05-06T10:05:30 Z surgutti Distributing Candies (IOI21_candies) C++17
8 / 100
 298 ms 29236 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] = mini[pos] = maxi[pos] = 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 sumi[1] - mini[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 + 1, v[i]});
		events.push_back(Event{r[i] + 1, i + 1, 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 26952 KB Output is correct
2 Correct 298 ms 29236 KB Output is correct
3 Correct 245 ms 29192 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -