Submission #1127207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127207		cppenjoyer	Distributing Candies (IOI21_candies)	C++20	100 / 100	460 ms	49096 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> iii;
const int MAXN = 200005;
const ll inf = 1e18;
struct node{
	int s, e, m; ll mx, mn, lazy;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; mx = mn = lazy = 0;
		if (s != e){
			l = new node(s, m); r = new node(m + 1, e);
		}
	}
	void push(ll v){
		mx += v; mn += v;
		lazy += v;
	}
	void propo(){
		if (s == e) return;
		if (lazy != 0){
			l->push(lazy); r->push(lazy);
			lazy = 0;
		}
	}
	void update(int x, int y, ll v){
		if (x == s && y == e){
			push(v); return;
		}
		propo();
		if (y <= m) l->update(x, y, v);
		else if (x > m) r->update(x, y, v);
		else{
			l->update(x, m, v); r->update(m + 1, y, v);
		}
		mx = max(l->mx, r->mx); mn = min(l->mn, r->mn);
	}
	ll query(int x){
		if (s == e) return mx;
		propo();
		if (x <= m) return l->query(x);
		else return r->query(x);
	}
	iii find(ll omx, ll omn, ll range){
		if (s == e) return {s, omx, omn};
		propo();
		ll nmx = max(omx, r->mx), nmn = min(omn, r->mn);
		if (nmx - nmn <= range) return l->find(nmx, nmn, range);
		else return r->find(omx, omn, range);
	}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
	int nums = c.size(), queries = l.size();
	vector<vector<int>> rsv(nums), rev(nums);
	for (int q = 0; q < queries; q++){
		rsv[l[q]].push_back(q);
		rev[r[q]].push_back(q);
	}
	node *root = new node(-2, queries - 1);
	root->update(-2, -2, inf);
	vector<int> ans(nums);
	for (int i = 0; i < nums; i++){
		for (int q : rsv[i]) root->update(q, queries - 1, v[q]);
		ll fid, mx, mn; tie(fid, mx, mn) = root->find(-inf, inf, c[i]);
		ll fv = root->query(fid), ev = root->query(queries - 1);
		if (fv > mx) ans[i] = ev - mn;
		else ans[i] = c[i] - (mx - ev);
		for (int q : rev[i]) root->update(q, queries - 1, -v[q]);
	}
	return ans;
}

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