oj.uz

답안 #911996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911996 2024-01-19T06:56:06 Z hhngriver 사탕 분배 (IOI21_candies) C++17
0 / 100
 332 ms 24080 KB 
#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

#define FILENAME "1-04.in"
#define MAX_N 200005
#define MAX_Q 200005
#define MAX_LOG_N 20

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
	int last_value;
	int lazyadd[4 * MAX_N];
	int maxseg[4 * MAX_N];
	int minseg[4 * MAX_N];
	set<int> 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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 332 ms 24080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Incorrect 198 ms 17772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6552 KB Output is correct
3 Correct 116 ms 17792 KB Output is correct
4 Correct 44 ms 9284 KB Output is correct
5 Correct 156 ms 20152 KB Output is correct
6 Correct 159 ms 20216 KB Output is correct
7 Incorrect 155 ms 20204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -