oj.uz

Submission #698015

# Submission time Handle Problem Language Result Execution time Memory
698015 2023-02-11T20:19:51 Z Elvin_Fritl Distributing Candies (IOI21_candies) C++17
100 / 100
 569 ms 38100 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 0 ms 304 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 468 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 527 ms 36248 KB Output is correct
2 Correct 547 ms 35472 KB Output is correct
3 Correct 569 ms 35356 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 317 ms 24892 KB Output is correct
3 Correct 86 ms 9772 KB Output is correct
4 Correct 494 ms 37296 KB Output is correct
5 Correct 514 ms 37708 KB Output is correct
6 Correct 507 ms 38100 KB Output is correct
7 Correct 548 ms 37324 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 162 ms 23356 KB Output is correct
4 Correct 79 ms 8756 KB Output is correct
5 Correct 275 ms 31028 KB Output is correct
6 Correct 273 ms 31676 KB Output is correct
7 Correct 278 ms 32352 KB Output is correct
8 Correct 266 ms 30908 KB Output is correct
9 Correct 286 ms 32408 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 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 468 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 527 ms 36248 KB Output is correct
7 Correct 547 ms 35472 KB Output is correct
8 Correct 569 ms 35356 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 317 ms 24892 KB Output is correct
11 Correct 86 ms 9772 KB Output is correct
12 Correct 494 ms 37296 KB Output is correct
13 Correct 514 ms 37708 KB Output is correct
14 Correct 507 ms 38100 KB Output is correct
15 Correct 548 ms 37324 KB Output is correct
16 Correct 0 ms 296 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 162 ms 23356 KB Output is correct
19 Correct 79 ms 8756 KB Output is correct
20 Correct 275 ms 31028 KB Output is correct
21 Correct 273 ms 31676 KB Output is correct
22 Correct 278 ms 32352 KB Output is correct
23 Correct 266 ms 30908 KB Output is correct
24 Correct 286 ms 32408 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 83 ms 8908 KB Output is correct
27 Correct 322 ms 24404 KB Output is correct
28 Correct 528 ms 36068 KB Output is correct
29 Correct 501 ms 36356 KB Output is correct
30 Correct 513 ms 36564 KB Output is correct
31 Correct 531 ms 36840 KB Output is correct
32 Correct 510 ms 37004 KB Output is correct