Submission #435591

#	Time	Username	Problem	Language	Result	Execution time	Memory
435591		Noam527	Distributing Candies (IOI21_candies)	C++17	100 / 100	1016 ms	35596 KiB

candies

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 3e18;
const int OO = 1;
using namespace std;

#include "candies.h"

struct info {
	ll mn, mx;
	int imn, imx;
	info() {
		mn = inf;
		mx = -inf;
		imn = imx = -1;
	}
	info(int index) {
		mn = mx = 0;
		imn = imx = index;
	}
	void use(const info &a) {
		if (mn > a.mn) {
			mn = a.mn;
			imn = a.imn;
		}
		if (mx < a.mx) {
			mx = a.mx;
			imx = a.imx;
		}
	}
};
void comb(info &a, const info b, const info &c) {
	a = b;
	a.use(c);
}
void pr(const info &a) {
	printf("(%lld, %d), (%lld, %d)\n", a.mn, a.imn, a.mx, a.imx);
}

// index 0 is saved! ye.
struct segtree {
	int n;
	vector<ll> tag;
	vector<info> t;
	segtree() {}
	segtree(int sz) {
		n = max(2, sz + 1);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
		tag.resize(2 * n, 0);
		for (int i = 0; i < n; i++) {
			t[i + n - 1] = info(i);
		}
		for (int i = n - 2; i >= 0; i--) {
			comb(t[i], t[2 * i + 1], t[2 * i + 2]);
		}
	}
	void push(int x) {
		t[x].mn += tag[x], t[x].mx += tag[x];
		if (x < n - 1) {
			tag[2 * x + 1] += tag[x];
			tag[2 * x + 2] += tag[x];
		}
		tag[x] = 0;
	}
	void fix(int x) {
		push(2 * x + 1), push(2 * x + 2);
		comb(t[x], t[2 * x + 1], t[2 * x + 2]);
	}
	void add(int l, int v) {
		add(l, n - 1, v, 0, 0, n - 1);
	}
	void add(int l, int r, int v) {
		add(l, r, v, 0, 0, n - 1);
	}
	void add(int l, int r, int v, int node, int nl, int nr) {
		if (nr < l || r < nl) return;
		if (l <= nl && nr <= r) {
			tag[node] += v;
			return;
		}
		push(node);
		int mid = (nl + nr) / 2;
		add(l, r, v, 2 * node + 1, nl, mid);
		add(l, r, v, 2 * node + 2, mid + 1, nr);
		fix(node);
	}
	info minimix(int l, int r) {
		if (l > r) return info();
		return minimix(l, r, 0, 0, n - 1);
	}
	info minimix(int l, int r, int node, int nl, int nr) {
		if (nr < l || r < nl) return info();
		push(node);
		if (l <= nl && nr <= r) {
			return t[node];
		}
		info res = info();
		int mid = (nl + nr) / 2;
		res.use(minimix(l, r, 2 * node + 1, nl, mid));
		res.use(minimix(l, r, 2 * node + 2, mid + 1, nr));
		return res;
	}
	info suffix(ll c) {
		push(0);
		if (t[0].mx - t[0].mn < c) return info();
		info cur = info(), tmp;
		int node = 0, nl = 0, nr = n - 1;
		while (node < n - 1) {
			int mid = (nl + nr) / 2;
			int left = 2 * node + 1, right = 2 * node + 2;
			push(left), push(right);
			comb(tmp, cur, t[right]);
			if (tmp.mx - tmp.mn < c) {
				cur = tmp;
				node = left;
				nr = mid;
			}
			else {
				node = right;
				nl = mid + 1;
			}
		}
		cur.use(t[node]);
		return cur;
	}
	ll get(int x) {
		int node = 0, nl = 0, nr = n - 1;
		while (node < n - 1) {
			push(node);
			int mid = (nl + nr) / 2;
			if (x <= mid) {
				nr = mid;
				node = 2 * node + 1;
			}
			else {
				nl = mid + 1;
				node = 2 * node + 2;
			}
		}
		push(node);
		return t[node].mn;
	}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	segtree T(q);
	vector<int> result(n);
	vector<vector<pair<int, int>>> upd(n);
	for (int i = 0; i < l.size(); i++) {
		int tim = i + 1;
		int val = v[i];
		upd[l[i]].emplace_back(tim, val);
		if (r[i] + 1 < n)
			upd[r[i] + 1].emplace_back(tim, -val);
	}
	for (int i = 0; i < n; i++) {
		for (const auto &p : upd[i]) {
			T.add(p.first, p.second);
		}
		info cur = T.suffix(c[i]);
		if (cur.imn == -1) {
			cur = T.minimix(0, q);
			if (cur.mn < 0)
				result[i] = T.get(q) - cur.mn;
			else
				result[i] = T.get(q);
		}
		else if (cur.imn < cur.imx) {
			result[i] = c[i] - (cur.mx - T.get(q));
		}
		else {
			result[i] = T.get(q) - cur.mn;
		}
	}
	return result;
}

void solve() {

	int n, q;
	cin >> n >> q;
	vector<int> c(n), l(q), r(q), v(q);
	for (auto &i : c) cin >> i;
	for (auto &i : l) cin >> i;
	for (auto &i : r) cin >> i;
	for (auto &i : v) cin >> i;
	vector<int> result = distribute_candies(c, l, r, v);
	for (const auto &i : result) cout << i << " "; cout << '\n';

	/*
	int n;
	cin >> n;
	segtree T(n);
	while (1) {
		string op;
		int l, r, v;
		cin >> op;
		if (op == "add") {
			cin >> l >> v;
			T.add(l, v);
		}
		else if (op == "minimix") {
			cin >> l >> r;
			info res = T.minimix(l, r);
			printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		}
		else if (op == "suffix") {
			cin >> v;
			info res = T.suffix(v);
			printf("(%lld, %d), (%lld, %d)\n", res.mn, res.imn, res.mx, res.imx);
		}
	}
	*/
}
/*
int main() {
	//ios::sync_with_stdio(0), cin.tie(0);
	int tst = 1;
	//cin >> tst;
	while (tst--) solve();
}
*/

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < l.size(); i++) {
      |                  ~~^~~~~~~~~~
candies.cpp: In function 'void solve()':
candies.cpp:193:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  193 |  for (const auto &i : result) cout << i << " "; cout << '\n';
      |  ^~~
candies.cpp:193:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  193 |  for (const auto &i : result) cout << i << " "; cout << '\n';
      |                                                 ^~~~

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