제출 #1242806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242806		franuch	사탕 분배 (IOI21_candies)	C++20	27 / 100	256 ms	26816 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

ll C;
struct Trans {
	ll l = 0, y = 0, r = C;
};

void merge(Trans &a, Trans b) {
	ll l = max(a.l, b.l - a.y + a.l);
	ll y;
	if (a.y <= b.l)
		y = b.y;
	else if (a.y <= b.r)
		y = a.y - b.l + b.y;
	else
		y = b.r - b.l + b.y;
	ll r = min(a.r, b.r - a.y + a.l);
	if (r <= l)
		l = r = 0;
	a = {l, y, r};
}

void add(Trans &a, ll x) {
	merge(a, {max(0ll, -x), max(x, 0ll), min(C, C - x)});
}

struct Tree {
	ll base;
	vc<Trans> t;

	Tree() = default;
	Tree(ll size) {
		base = 1;
		while (base < size)
			base *= 2;
		t.assign(2 * base, {0, 0, C});
	}

	void push(ll i, ll li, ll ri) {
		merge(t[li], t[i]);
		merge(t[ri], t[i]);
		t[i] = {0, 0, C};
	}

	void update(ll ql, ll qr, ll qx, ll i = 1, ll l = 0, ll r = -1) {
		if (r == -1)
			r = base - 1;
		if (qr < l or r < ql)
			return;
		if (ql <= l and r <= qr) {
			add(t[i], qx);
			return;
		}
		ll m = (l + r) / 2;
		ll li = 2 * i;
		ll ri = li + 1;
		push(i, li, ri);
		update(ql, qr, qx, li, l, m);
		update(ql, qr, qx, ri, m + 1, r);
	}

	void pushAll() {
		for (ll i = 1; i < base; i++)
			push(i, 2 * i, 2 * i + 1);
	}
};

ll n, q;
vc<ll> cap, ql, qr, qx, res;

void program() {
	Tree tree(n);
	for (ll i = 0; i < q; i++)
		tree.update(ql[i], qr[i], qx[i]);
	tree.pushAll();
	res.resize(n);
	for (ll i = 0; i < n; i++)
		res[i] = tree.t[i + tree.base].y;
}

vc<int> distribute_candies(vc<int> c, vc<int> l, vc<int> r, vc<int> v) {
	n = sz(c);
	q = sz(l);
	cap.assign(all(c));
	C = cap[0];
	ql.assign(all(l));
	qr.assign(all(r));
	qx.assign(all(v));
	program();
	vc<int> ret(all(res));
    return ret;
}

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