제출 #912090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912090		hhngriver	Distributing Candies (IOI21_candies)	C++17	100 / 100	362 ms	33872 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33