제출 #618904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618904		Temmie	사탕 분배 (IOI21_candies)	C++17	100 / 100	859 ms	38220 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33