Submission #601796

#	Time	Username	Problem	Language	Result	Execution time	Memory
601796		SeDunion	Distributing Candies (IOI21_candies)	C++17	0 / 100	5072 ms	363816 KiB

candies

#include "candies.h"
#include<algorithm>
#include<iostream>
#include <vector>

using namespace std;
using vi = vector<int>;
using ll = long long;

//f(a, l, r) = clamp(t[v]+a, l, r)
//f(x, L, R) = clamp(clamp(t[v]+a,l,r) + x, L, R)
//f(x, L, R) = clamp(clamp(t[v]+a+x,l+x,r+x), L, R)

const int N = 2e5 + 123;

struct lazy {
	ll a, l, r;
};

int n, q, C;

lazy tree[N << 2];

void apply(int v, lazy p) {
	tree[v].a += p.a;
	tree[v].l += p.a;
	tree[v].r += p.a;
	if (tree[v].r < p.l) tree[v].l = tree[v].r = p.l;
	else if (tree[v].l > p.r) tree[v].l = tree[v].r = p.r;
	else tree[v].l = max(tree[v].l, p.l), tree[v].r = min(tree[v].r, p.r);
}

void push(int v, int l, int r) {
	if (r - l > 1) apply(v << 1, tree[v]), apply(v<<1|1, tree[v]), tree[v].a = 0, tree[v].l = 0, tree[v].r = C;
}

void upd(int L, int R, lazy p, int l = 0, int r = n, int v = 1) {
	push(v, l, r);
	if (L <= l && r <= R) {
		apply(v, p);
		push(v, l, r);
		return;
	} 
	if (L >= r || l >= R) {
		return;
	}
	int m = (l + r) >> 1;
	upd(L, R, p, l, m, v << 1);
	upd(L, R, p, m, r, v<<1|1);
}

void show(int l, int r, int v, vector<int>&ans) {
	push(v, l, r);
	if (r - l == 1) {

		cout << (ans[l] = clamp(tree[v].a, tree[v].l, tree[v].r)) << ' ';
		return;
	}
	int m = (l + r) >> 1;
	show(l, m, v << 1, ans);
	show(m, r, v<<1|1, ans);
}

vi distribute_candies(vi c, vi l, vi r, vi v) {
	n = c.size();
	q = l.size();
	C = c[0];
	for (int i = 0 ; i < N*4 ; ++ i) tree[i].a = 0, tree[i].l = 0, tree[i].r = c[0];
	vector<int>ans(n);
	for (int i = 0 ; i < q ; ++ i) {
		lazy cur;
		cur.l = 0, cur.r = c[0], cur.a = v[i];
		upd(l[i], r[i]+1, cur);
		cout << endl;
		show(0, n, 1, ans);
		cout << endl;
	}
	cout << endl;
	show(0, n, 1, ans);
	cout << endl;
	return ans;
}

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