Submission #1245078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245078		nicolo_010	Distributing Candies (IOI21_candies)	C++20	8 / 100	151 ms	16860 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
template <typename T>
using ve = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i=k;i<n;i++)

ve<ll> a;

struct SegTree {
	ve<ll> lazy;
	SegTree (int n) {
		lazy.assign(4*n, 0);
	}

	void prop(int p, int l, int r) {
		if (l == r) {
			a[l] += lazy[p];
		}
		else {
			lazy[2*p] += lazy[p];
			lazy[2*p+1] += lazy[p];
		}
		lazy[p] = 0;
	}

	void query(int p, int l, int r, int i, int j, int k) {
		if (l > j || r < i) return;
		if (lazy[p]) prop(p, l, r);
		if (i <= l && r <= j) {
			lazy[p] += k;
			prop(p, l, r);
		}
		else {
			query(2*p, l, (l+r)/2, i, j, k);
			query(2*p+1, (l+r)/2+1, r, i, j, k);
		}
	}

	void point(int p, int l, int r, int i) {
		if (lazy[p]) prop(p, l, r);
		if (l == r) return;
		else {
			point(2*p, l, (l+r)/2, i);
			point(2*p+1, (l+r)/2+1, r, i);
		}
	}
};

ve<int> distribute_candies(ve<int> c, ve<int> l, ve<int> r, ve<int> v) {
	int n = c.size();
	int q = l.size();
	a.assign(n, 0);
	SegTree st(n);
	ve<ll> mx(n);
	rep(i, 0, n)mx[i] = c[i];
	rep(i, 0, q) {
		st.query(1, 0, n-1, l[i], r[i], v[i]);
	}
	st.point(1, 0, n-1, 0);
	rep(i, 0, n) a[i] = min(a[i], mx[i]);
	ve<int> ans(n);
	rep(i, 0, n) ans[i] = a[i];
	return ans;
}

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