Submission #1106306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106306		pit4h	Distributing Candies (IOI21_candies)	C++17	3 / 100	5178 ms	1736652 KiB

candies

#include "candies.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
#define mp make_pair
#define eb emplace_back
#define x first
#define y second
#define sz(x)int((x).size())
#define all(x)(x).begin(),(x).end()
#define rep(i,a,b)for(int i=(a);i<(b);i++)
#define per(i,a,b)for(int i=(b)-1;i>=(a);i--)
bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto&e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define debug(...){}
#endif

const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, base = (1 << 19);

const ll INF = 1e18;

vi c, cnt;

int n, q;

vector<pair<ll, int>> tree[2 * base + 1];

void ins(int l, int r, pair<ll, int> val) {
	l += base;
	r += base;
	tree[l].eb(val);
	debug("tree", l, val);
	if (l != r) {
		tree[r].eb(val);
		debug("tree", r, val);
	}
	while (l / 2 != r / 2) {
		if (l % 2 == 0) {
			tree[l+1].eb(val);
			debug("tree", l+1, val);
		}
		if (r % 2 == 1) {
			tree[r-1].eb(val);
			debug("tree", r-1, val);
		}
		l /= 2;
		r /= 2;
	}
}

struct Solver {
	ll pref[2*base], lazy[2*base], tree_min[2*base], tree_max[2*base];
	ll total;
	void init(int siz) {
		total=0;
		rep(i,0,2*base) {
			pref[i] = lazy[i] = 0;
			tree_min[i] = 0;
			tree_max[i] = 0;
		}
	}
	vector<vector<pair<int, vector<ll>>>> rollbacks;
	void ins(int i, ll v) {
		total += v;
		rollbacks.eb(vector<pair<int,vector<ll>>>());
		add(1, i, v);
	}
	ll get(ll cap) {
		rollbacks.eb(vector<pair<int,vector<ll>>>());
		auto [ceil, sub] = rec(cap);	
		debug(ceil, sub, total);
		if (ceil == -1) {
			return total - tree_min[1];
		}
		return total - sub + cap * ceil;
	}
	void undo(ll v) {
		debug("undo", v);
		total -= v;
		assert(!rollbacks.empty());
		vector<pair<int, vector<ll>>> vec = rollbacks.back();
		reverse(all(vec));
		for (auto& [id, values]: vec) {
			assert(sz(values) == 4);
			pref[id] = values[0];
			lazy[id] = values[1];
			tree_min[id] = values[2];
			tree_max[id] = values[3];
		}
		rollbacks.pop_back();
	}
	void push(int id, ll v) {
		rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));

		pref[id] += v;
		lazy[id] += v;
		tree_min[id] += v;
		tree_max[id] += v;
	}
	void add(int id, int i, ll v, int rl=0, int rr=base-1) {
		rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));

		if (rr < i) return;
		if (rl >= i) {
			push(id, v);
			return;
		}

		push(id*2,lazy[id]);
		push(id*2+1,lazy[id]);
		lazy[id]=0;

		int mid = (rl+rr)/2;
		add(id*2,i,v,rl,mid);
		add(id*2+1,i,v,mid+1,rr);

		tree_min[id] = min(tree_min[id*2], tree_min[id*2+1]);
		tree_max[id] = max(tree_max[id*2], tree_max[id*2+1]);
	}

	pair<int,ll> rec(ll cap, int id=1, int rl=0,  int rr=base-1, ll suf_min=INF, ll suf_max=-INF) {
		debug("rec", cap, id, rl, rr, suf_min, suf_max, tree_min[id], tree_max[id]);

		rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));
		if (max(suf_max, tree_max[id]) - min(suf_min, tree_min[id]) < cap) {
			return mp(-1,0LL);	
		}
		if (rl == rr) {
			if (suf_max - pref[id] >= cap) {
				return mp(1,suf_max);
			}
			else {
				assert(pref[id] - suf_min >= cap);
				return mp(0,suf_min);
			}
		}

		push(id*2,lazy[id]);
		push(id*2+1,lazy[id]);
		lazy[id]=0;

		int mid=(rl+rr)/2;
		pair<int,ll> res = rec(cap, id*2+1, mid+1, rr, suf_min, suf_max);
		if (res != mp(-1,0LL)) {
			return res;
		}
		ll new_min = min(suf_min, tree_min[id*2+1]), new_max = max(suf_max, tree_max[id*2+1]);
		return rec(cap, id*2, rl, mid, new_min, new_max);
	}
} solver;

void solve(int id, int l, int r) {
	debug(id, l, r);

	for (auto& [v, i]: tree[id]) {
		debug("ins", i, v);
		solver.ins(i, v);	
	}

	if (l == r) {
		if (l < n) {
			cnt[l] = solver.get(c[l]);
			solver.undo(0);
		}
	}
	else {
		int mid = (l+r)/2;
		solve(id * 2, l, mid);
		solve(id * 2 + 1, mid + 1, r);
	}

	vector<ll> to_undo;
	for (auto& [v, i]: tree[id]) {
		to_undo.eb(v);
	}
	reverse(all(to_undo));
	for (ll v: to_undo) {
		solver.undo(v);
	}
}

vector<int> distribute_candies(vector<int> _c, vector<int> l,
                               vector<int> r, vector<int> v) {
	c = _c;
    n = c.size(); q = sz(l);
    vector<int> s(n);
	cnt.resize(n); rep(i,0,n) cnt[i] = 0;

	rep(i,0,q) {
		debug("INS", l[i], r[i], v[i], i);
		ins(l[i], r[i], mp(v[i], i+1));
	}

	solver.init(q);
	solve(1, 0, base - 1);

	rep(i,0,n) s[i] = cnt[i];
    return s;
}

Compilation message (stderr)

candies.cpp:16:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |            ^~~~
candies.cpp:16:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |                   ^~~~
candies.cpp:17:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |            ^~~~
candies.cpp:17:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |                   ^~~~

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