Submission #536018

#	Time	Username	Problem	Language	Result	Execution time	Memory
536018		grt	Distributing Candies (IOI21_candies)	C++17	100 / 100	540 ms	38092 KiB

candies

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

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

const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;
vector<pi>evs[nax];

struct Node {
	ll g, mi, mx;
};

Node T[(1 << 19)];

void puttag(int v, ll x) {
	T[v].mi += x;
	T[v].mx += x;
	T[v].g += x;
}

void push(int v) {
	puttag(v << 1, T[v].g);
	puttag(v << 1 | 1, T[v].g);
	T[v].g = 0;
}

void merge(int v) {
	T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi) + T[v].g;
	T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx) + T[v].g;
}

void upd(int a, int b, ll x, int l = 0, int r = q, int v = 1) {
	if(a <= l && r <= b) {
		puttag(v, x);
		return;
	}
	push(v);
	int mid = (l + r) >> 1;
	if(a <= mid) upd(a, b, x, l, mid, v << 1);
	if(mid < b) upd(a, b, x, mid + 1, r, v << 1 | 1);
	merge(v);
}

tuple<int,ll,ll,ll> ask(int k) {
	int v = 1, l = 0, r = q;
	ll mi = INF, mx = -INF;
	while(l != r) {
		int mid = (l + r) >> 1;
		push(v);
		if(max(mx, T[v << 1 | 1].mx) - min(mi, T[v << 1 | 1].mi) > k) {
			v = v << 1 | 1;
			l = mid + 1;
		} else {
			mx = max(mx, T[v << 1 | 1].mx);
			mi = min(mi, T[v << 1 | 1].mi);
			v = v << 1;
			r = mid;
		}
	}
	mi = min(mi, T[v].mi);
	mx = max(mx, T[v].mx);
	return {l, mi, mx, T[v].mi};
}

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
	n = (int)_c.size();
	q = (int)_l.size();
	for(int i = 0; i < q; ++i) {
		evs[_l[i]].emplace_back(i + 1, _v[i]);
		evs[_r[i] + 1].emplace_back(i + 1, -_v[i]);
	}
	vi ans(n);
	ll sum = 0;
	for(int i = 0; i < n; ++i) {
		for(auto &[a,b] : evs[i]) {
			upd(a, q, b);
			sum += b;
		}
		auto [p, a, b, val] = ask(_c[i]);
		if(b - a <= _c[i]) {
			ans[i] = sum - a;
		} else {
			if(val == a) {
				//cerr << _c[i] + sum - b << "\n";
				ans[i] = _c[i] + sum - b;
			} else {
				assert(val == b);
				//cerr << sum - a << "\n";
				ans[i] = sum - a;
			}
		}
	}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
//}

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