oj.uz

Submission #774008

# Submission time Handle Problem Language Result Execution time Memory
774008 2023-07-05T10:51:22 Z SanguineChameleon Distributing Candies (IOI21_candies) C++17
100 / 100
 702 ms 44576 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 11 ms 23892 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 13 ms 23896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 37872 KB Output is correct
2 Correct 651 ms 41944 KB Output is correct
3 Correct 702 ms 41772 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23700 KB Output is correct
2 Correct 155 ms 32972 KB Output is correct
3 Correct 213 ms 29532 KB Output is correct
4 Correct 660 ms 43780 KB Output is correct
5 Correct 604 ms 44192 KB Output is correct
6 Correct 562 ms 44576 KB Output is correct
7 Correct 559 ms 43928 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23812 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 89 ms 31688 KB Output is correct
4 Correct 193 ms 26240 KB Output is correct
5 Correct 482 ms 33988 KB Output is correct
6 Correct 460 ms 33968 KB Output is correct
7 Correct 413 ms 33984 KB Output is correct
8 Correct 483 ms 33896 KB Output is correct
9 Correct 533 ms 34016 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 11 ms 23892 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 13 ms 23896 KB Output is correct
6 Correct 588 ms 37872 KB Output is correct
7 Correct 651 ms 41944 KB Output is correct
8 Correct 702 ms 41772 KB Output is correct
9 Correct 10 ms 23700 KB Output is correct
10 Correct 155 ms 32972 KB Output is correct
11 Correct 213 ms 29532 KB Output is correct
12 Correct 660 ms 43780 KB Output is correct
13 Correct 604 ms 44192 KB Output is correct
14 Correct 562 ms 44576 KB Output is correct
15 Correct 559 ms 43928 KB Output is correct
16 Correct 10 ms 23812 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 89 ms 31688 KB Output is correct
19 Correct 193 ms 26240 KB Output is correct
20 Correct 482 ms 33988 KB Output is correct
21 Correct 460 ms 33968 KB Output is correct
22 Correct 413 ms 33984 KB Output is correct
23 Correct 483 ms 33896 KB Output is correct
24 Correct 533 ms 34016 KB Output is correct
25 Correct 10 ms 23780 KB Output is correct
26 Correct 191 ms 27512 KB Output is correct
27 Correct 166 ms 35616 KB Output is correct
28 Correct 626 ms 42444 KB Output is correct
29 Correct 597 ms 42828 KB Output is correct
30 Correct 593 ms 43096 KB Output is correct
31 Correct 554 ms 43296 KB Output is correct
32 Correct 537 ms 43300 KB Output is correct