Submission #774008

#	Time	Username	Problem	Language	Result	Execution time	Memory
774008		SanguineChameleon	Distributing Candies (IOI21_candies)	C++17	100 / 100	702 ms	44576 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxN = 2e5 + 20;
vector<pair<int, int>> events[maxN];

struct node {
	long long mx, mi, lazy;

	node(): mx(0), mi(0), lazy(0) {};

	node(long long _mx, long long _mi): mx(_mx), mi(_mi), lazy(0) {};
};

node tree[maxN * 4];

node merge(node left, node right) {
	return node(max(left.mx, right.mx), min(left.mi, right.mi));
}

void add(int id, long long val) {
	tree[id].mx += val;
	tree[id].mi += val;
	tree[id].lazy += val;
}

void push(int id) {
	add(id * 2, tree[id].lazy);
	add(id * 2 + 1, tree[id].lazy);
	tree[id].lazy = 0;
}

void update(int id, int lt, int rt, int pos, int val) {
	if (lt == rt) {
		add(id, val);
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (pos >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, pos, val);
	}
	else {
		add(id * 2 + 1, val);
		update(id * 2, lt, mt, pos, val);
	}
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}

node get(int id, int lt, int rt, int pos) {
	if (lt == rt) {
		return tree[id];
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (pos >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, pos);
	}
	else {
		return merge(get(id * 2, lt, mt, pos), tree[id * 2 + 1]);
	}
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	int N = C.size();
	int Q = L.size() + 2;
	for (int i = 0; i < Q - 2; i++) {
		events[L[i]].emplace_back(i + 3, V[i]);
		events[R[i] + 1].emplace_back(i + 3, -V[i]);
	}
	update(1, 1, Q, 1, inf);
	update(1, 1, Q, 2, -inf);
	vector<int> res(N);
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		for (auto e: events[i]) {
			update(1, 1, Q, e.first, e.second);
			sum += e.second;
		}
		int lt = 1;
		int rt = Q;
		int last = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			node M = get(1, 1, Q, mt);
			if (M.mx - M.mi <= C[i]) {
				last = mt;
				rt = mt - 1;
			}
			else {
				lt = mt + 1;
			}
		}
		node M1 = get(1, 1, Q, last);
		node M2 = get(1, 1, Q, last - 1);
		res[i] = sum - (M1.mi == M2.mi ? M1.mi : (M1.mx - C[i]));
	}
	return res;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33