Submission #518810

#	Time	Username	Problem	Language	Result	Execution time	Memory
518810		Asymmetry	Distributing Candies (IOI21_candies)	C++17	100 / 100	355 ms	38100 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

struct node {
	long long mn, mx, ps;
};

int n, q, com, p;
long long mn, mx, all;
vector<node> st;

void ins(int x, int l, int r, int ll, int rr, int w) {
	if (l > rr || ll > r) {
		return;
	}
	if (ll <= l && r <= rr) {
		st[x].mx += w;
		st[x].mn += w;
		st[x].ps += w;
		return;
	}
	int ls = x << 1;
	ins(ls, l, (l + r) / 2, ll, rr, w);
	ins(ls ^ 1, (l + r) / 2 + 1, r, ll, rr, w);
	st[x].mx = max(st[ls].mx, st[ls ^ 1].mx) + st[x].ps;
	st[x].mn = min(st[ls].mn, st[ls ^ 1].mn) + st[x].ps;
}

void suf(int x, int w, long long add) {
	if (x >= com) {
		mn = min(mn, st[x].mn + add);
		mx = max(mx, st[x].mx + add);
		p = mn == (st[x].mn + add);
		return;
	}
	add += st[x].ps;
	int ls = x << 1;
	if (max(mx, st[ls ^ 1].mx + add) - min(mn, st[ls ^ 1].mn + add) >= w) { // idziemy w prawo
		suf(ls ^ 1, w, add);
	}
	else {
		mx = max(mx, st[ls ^ 1].mx + add);
		mn = min(mn, st[ls ^ 1].mn + add);
		suf(ls, w, add);
	}
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size();
	q = l.size();
	com = 1;
	while (com < q + 1) {
		com <<= 1;
	}
	st.resize(com << 1);
	vector<pair<int, int>> z[n + 1];
	for (int i = 0; i < q; ++i) {
		z[l[i]].push_back({i + 1, v[i]});
		z[r[i] + 1].push_back({i + 1, -v[i]});
	}
	vector<int> odp(n);
	for (int i = 0; i < n; ++i) {
		for (auto j : z[i]) {
			all += j.second;
			ins(1, 0, com - 1, j.first, com, j.second);
		}
		if (st[1].mx - st[1].mn <= c[i]) {
			odp[i] = all - st[1].mn;
			continue;
		}
		mn = 1e18;
		mx = -1e18;
		p = 0;
		suf(1, c[i], 0);
		//~ printf("I = %d | %lld | %d | %lld %lld\n", i, all, p, mn, mx);
		if (p) {
			odp[i] = all + c[i] - mx;
		}
		else {
			odp[i] = all - mn;
		}
	}
	return odp;
}

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