oj.uz

Submission #912090

# Submission time Handle Problem Language Result Execution time Memory
912090 2024-01-19T07:28:54 Z hhngriver Distributing Candies (IOI21_candies) C++17
100 / 100
 362 ms 33872 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define MAX_N 200005
#define MAX_Q 200005

struct action {
	int amount;
	int at_node;
	action(int amt, int node) {
		amount = amt;
		at_node = node;
	}
};

struct binary_segment_tree {
	int total_nodes;
	int start_node; // start node is the starting point where nothing happens yet
	long long last_value;
	long long lazyadd[4 * MAX_N];
	long long maxseg[4 * MAX_N];
	long long minseg[4 * MAX_N];
	set<long long> upper_bound;

	void init(int n) {
		total_nodes = pow(2, int(log(n) / log(2)) + 2);
		start_node = total_nodes / 2;
		for (int i = 0; i < (log(n) / log(2) + 1); i++)
			upper_bound.insert(pow(2, i));
		last_value = 0;
	}

	void update_max_min(int child, int parent, int sibling) {
		while (parent > 0) {
			maxseg[parent] = std::max(maxseg[child] + lazyadd[child],
					maxseg[sibling] + lazyadd[sibling]);
			minseg[parent] = std::min(minseg[child] + lazyadd[child],
					minseg[sibling] + lazyadd[sibling]);
			child = parent;
			parent = child / 2;
			sibling = child ^ 1;
		};
	}

	void update(action act) {
		int child = act.at_node + start_node + 1;
		int sibling, parent;
		last_value += act.amount;
		do {
			sibling = child ^ 1;
			parent = child / 2;
			if (child < sibling) {
				child = parent;
			} else {
				lazyadd[child] += act.amount;
				update_max_min(child, parent, sibling);
				if (upper_bound.find(parent + 1) != upper_bound.end()) // parent not at the right border of the tree
					break;
				else
					child = parent + 1;
			}
		} while (parent > 0);
	}

	int find_candies(int capacity) {
		if (maxseg[1] - minseg[1] <= capacity) {
			return last_value - minseg[1];
		} else {
			int parent = 1;
			int left_child, right_child;
			long long big = -std::numeric_limits<long long>::max();
			long long small = std::numeric_limits<long long>::max();
			long long current_lazy = lazyadd[1];
			long long temp_big, temp_small;
			do {
				left_child = parent * 2;
				right_child = left_child + 1;
				temp_big = std::max(big,
						maxseg[right_child] + lazyadd[right_child]
								+ current_lazy);
				temp_small = std::min(small,
						minseg[right_child] + lazyadd[right_child]
								+ current_lazy);
				if (temp_big - temp_small >= capacity) {
					parent = right_child;
				} else {
					big = temp_big;
					small = temp_small;
					parent = left_child;
				}
				current_lazy += lazyadd[parent];
			} while (parent < start_node);
			if (current_lazy < last_value) {
				return capacity - (big - last_value);
			} else {
				return last_value - small;
			}
		}
	}
} seg_tree;

vector<action> act_list[MAX_N];

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R,
		vector<int> V) {
	int n_node = L.size(); // number of distributions
	int n_box = C.size();
	vector<int> ans(n_box);

	for (int i = 0; i < n_node; i++) {
		act_list[L[i]].push_back(action(V[i], i)); // add this action on the segment tree if beginning distribution
		act_list[R[i] + 1].push_back(action(-V[i], i)); // remove this action on the segment tree if ending distribution
	}

	seg_tree.init(n_node + 1);
	for (int i = 0; i < n_box; i++) {
		for (auto act : act_list[i])
			seg_tree.update(act);
		ans[i] = seg_tree.find_candies(C[i]);
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 7000 KB Output is correct
3 Correct 3 ms 6744 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 27724 KB Output is correct
2 Correct 290 ms 29780 KB Output is correct
3 Correct 316 ms 31628 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 206 ms 21216 KB Output is correct
3 Correct 45 ms 12504 KB Output is correct
4 Correct 302 ms 33620 KB Output is correct
5 Correct 347 ms 33872 KB Output is correct
6 Correct 348 ms 32600 KB Output is correct
7 Correct 298 ms 32216 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 109 ms 21416 KB Output is correct
4 Correct 42 ms 9284 KB Output is correct
5 Correct 157 ms 23840 KB Output is correct
6 Correct 158 ms 23840 KB Output is correct
7 Correct 156 ms 23988 KB Output is correct
8 Correct 161 ms 27572 KB Output is correct
9 Correct 152 ms 28856 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 7000 KB Output is correct
3 Correct 3 ms 6744 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 326 ms 27724 KB Output is correct
7 Correct 290 ms 29780 KB Output is correct
8 Correct 316 ms 31628 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 206 ms 21216 KB Output is correct
11 Correct 45 ms 12504 KB Output is correct
12 Correct 302 ms 33620 KB Output is correct
13 Correct 347 ms 33872 KB Output is correct
14 Correct 348 ms 32600 KB Output is correct
15 Correct 298 ms 32216 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 109 ms 21416 KB Output is correct
19 Correct 42 ms 9284 KB Output is correct
20 Correct 157 ms 23840 KB Output is correct
21 Correct 158 ms 23840 KB Output is correct
22 Correct 156 ms 23988 KB Output is correct
23 Correct 161 ms 27572 KB Output is correct
24 Correct 152 ms 28856 KB Output is correct
25 Correct 2 ms 6748 KB Output is correct
26 Correct 43 ms 10320 KB Output is correct
27 Correct 204 ms 23836 KB Output is correct
28 Correct 302 ms 30676 KB Output is correct
29 Correct 314 ms 32680 KB Output is correct
30 Correct 362 ms 32084 KB Output is correct
31 Correct 314 ms 33056 KB Output is correct
32 Correct 308 ms 31568 KB Output is correct