Submission #435145

#	Time	Username	Problem	Language	Result	Execution time	Memory
435145		Kevin_Zhang_TW	Distributing Candies (IOI21_candies)	C++17	100 / 100	1758 ms	31940 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "candies.h"

const int MAX_N = 200010;
const ll inf = 1ll << 59;

int n, m;
struct node {
	ll mx, mn, at;
	void operator += (ll v) { mx += v, mn += v, at += v; }
	node (ll a, ll b) : mx(a), mn(b), at(0) {}
	node (ll v) : at(0), mx(v), mn(v) {}
	node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
	node () : mx(0), mn(0), at(0) {}
	bool valid(int c) { return mx - mn <= c; }
};

vector<pair<ll,ll>> op[MAX_N];

struct sgt {
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
	}
	void push(int i) {
		if (i >= n) return;
		val[i<<1] += val[i].at;
		val[i<<1|1] += val[i].at;
		val[i].at = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void add(int l, int r, ll v) {
		l += n, r += n;
		int sl = l, sr = r;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;)
			upd(sl), upd(sr);
	}
	node qry(int l, int r) {
		l += n, r += n;
		for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
		node ret(-inf, inf);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) ret = node(ret, val[l++]);
			if (r&1) ret = node(ret, val[--r]);
		}
		return ret;
	}
}tree(0);

int qry(int c) {
	auto s0 = tree.qry(0, m);
	ll all = tree.qry(m-1, m).mx;
	if (s0.mx - s0.mn <= c) {
		return all - s0.mn;
	}
	int l = 0, r = m-1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (tree.qry(mid, m).valid(c))
			r = mid;
		else
			l = mid+1;
	}
	assert(l > 0);
	ll v = tree.qry(l-1, l).mx;
	auto sl = tree.qry(l, m);
	if (sl.mx > v + c) {
		return c + (all - sl.mx);
	}
	else return all - sl.mn;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size(), m = l.size();
	for (int i = 0;i < m;++i) {
		op[l[i]].pb(i+1, v[i]);
		op[r[i]+1].pb(i+1, -v[i]);
	}
	++m;
	tree = sgt(m);
	vector<int> res(n);
	for (int i = 0;i < n;++i) {
		for (auto [j, w] : op[i]) 
			tree.add(j, m, w);
		res[i] = qry(c[i]);
	}
	return res;
}

Compilation message (stderr)

candies.cpp: In constructor 'node::node(ll)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  node (ll v) : at(0), mx(v), mn(v) {}
      |  ^~~~
candies.cpp: In constructor 'node::node(node, node)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:28:2: warning:   when initialized here [-Wreorder]
   28 |  node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
      |  ^~~~
candies.cpp: In function 'int qry(int)':
candies.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   mid = l + r >> 1;
      |         ~~^~~

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