oj.uz

Submission #618904

# Submission time Handle Problem Language Result Execution time Memory
618904 2022-08-02T08:16:52 Z Temmie Distributing Candies (IOI21_candies) C++17
100 / 100
 859 ms 38220 KB 
#include <bits/stdc++.h>

struct Seg {
	
	struct Item {
		
		long long min = 0, max = 0;
		long long lazy = 0;
		
		constexpr friend Item merge(Item l, Item r) {
			return { std::min(l.min, r.min), std::max(l.max, r.max), l.lazy + r.lazy };
		}
		
	};
	
	int size;
	std::vector <Item> v;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1);
	}
	
	inline void push(int now, int l, int r) {
		v[now].min += v[now].lazy;
		v[now].max += v[now].lazy;
		if (r - l - 1) {
			v[now * 2 + 1].lazy += v[now].lazy;
			v[now * 2 + 2].lazy += v[now].lazy;
		}
		v[now].lazy = 0;
	}
	
	void update(int l, int r, long long val) {
		update(l, r, val, 0, 0, size);
	}
	
	void update(int tl, int tr, long long val, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return;
		}
		if (l >= tl && r <= tr) {
			v[now].lazy += val;
			return;
		}
		int mid = (l + r) >> 1;
		push(now, l, r);
		update(tl, tr, val, now * 2 + 1, l, mid);
		update(tl, tr, val, now * 2 + 2, mid, r);
		push(now * 2 + 1, l, mid);
		push(now * 2 + 2, mid, r);
		v[now] = merge(v[now * 2 + 1], v[now * 2 + 2]);
	}
	
	int get_ind(int capacity, int now, int l, int r, long long& min, long long& max) {
		if (!(r - l - 1)) {
			return now;
		}
		int mid = (l + r) >> 1;
		push(now, l, r);
		push(now * 2 + 1, l, mid);
		push(now * 2 + 2, mid, r);
		long long new_max = std::max(v[now * 2 + 2].max, max);
		long long new_min = std::min(v[now * 2 + 2].min, min);
		if (new_max - new_min < (long long) capacity) {
			return get_ind(capacity, now * 2 + 1, l, mid, min = new_min, max = new_max);
		}
		return get_ind(capacity, now * 2 + 2, mid, r, min, max);
	}
	
	long long query(int capacity) {
		int ind = 0;
		for (int l = 0, r = size; r - l - 1; l = (l + r) >> 1) {
			push(ind, l, r);
			push(ind * 2 + 1, l, (l + r) >> 1);
			push(ind * 2 + 2, (l + r) >> 1, r);
			ind = ind * 2 + 2;
		}
		long long min = 1LL << 60;
		long long max = -min;
		return v[get_ind(capacity, 0, 0, size, min, max)].min < min ? capacity - max + v[ind].min : v[ind].min - min;
	}
	
};

std::vector <int> distribute_candies(std::vector <int> c, std::vector <int> l, std::vector <int> r, std::vector <int> v) {
	std::vector <std::vector <std::pair <int, int>>> upd(c.size() + 1);
	for (int i = 0; i < (int) v.size(); i++) {
		upd[l[i]].emplace_back(i, v[i]);
		upd[r[i] + 1].emplace_back(i, -v[i]);
	}
	Seg seg(v.size() + 2);
	seg.update(0, seg.size, 1LL << 60);
	seg.update(1, seg.size, -(1LL << 60));
	std::vector <int> ans(c.size());
	for (int i = 0; i < (int) c.size(); i++) {
		for (auto p : upd[i]) {
			seg.update(p.first + 2, seg.size, p.second);
		}
		ans[i] = seg.query(c[i]);
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 4 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 36236 KB Output is correct
2 Correct 600 ms 35416 KB Output is correct
3 Correct 636 ms 35300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 546 ms 24884 KB Output is correct
3 Correct 98 ms 9676 KB Output is correct
4 Correct 629 ms 37200 KB Output is correct
5 Correct 738 ms 37700 KB Output is correct
6 Correct 853 ms 38220 KB Output is correct
7 Correct 611 ms 37436 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 181 ms 20740 KB Output is correct
4 Correct 99 ms 7540 KB Output is correct
5 Correct 344 ms 27504 KB Output is correct
6 Correct 309 ms 27768 KB Output is correct
7 Correct 337 ms 27812 KB Output is correct
8 Correct 365 ms 27736 KB Output is correct
9 Correct 348 ms 27780 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 614 ms 36236 KB Output is correct
7 Correct 600 ms 35416 KB Output is correct
8 Correct 636 ms 35300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 546 ms 24884 KB Output is correct
11 Correct 98 ms 9676 KB Output is correct
12 Correct 629 ms 37200 KB Output is correct
13 Correct 738 ms 37700 KB Output is correct
14 Correct 853 ms 38220 KB Output is correct
15 Correct 611 ms 37436 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 181 ms 20740 KB Output is correct
19 Correct 99 ms 7540 KB Output is correct
20 Correct 344 ms 27504 KB Output is correct
21 Correct 309 ms 27768 KB Output is correct
22 Correct 337 ms 27812 KB Output is correct
23 Correct 365 ms 27736 KB Output is correct
24 Correct 348 ms 27780 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 95 ms 8748 KB Output is correct
27 Correct 413 ms 24444 KB Output is correct
28 Correct 659 ms 35876 KB Output is correct
29 Correct 589 ms 36336 KB Output is correct
30 Correct 763 ms 36564 KB Output is correct
31 Correct 799 ms 36720 KB Output is correct
32 Correct 859 ms 36828 KB Output is correct