Submission #971918

#	Time	Username	Problem	Language	Result	Execution time	Memory
971918		penguin133	Distributing Candies (IOI21_candies)	C++17	0 / 100	387 ms	51468 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#include "candies.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll cap;

struct dat{
	ll cur_sum, mx, mn;
};

dat comb(dat a, dat b){
	dat ans;
	ans.cur_sum = a.cur_sum + b.cur_sum;
	if(a.cur_sum + b.mx > cap){
		ans.cur_sum = cap + b.cur_sum - b.mx;
	}
	if(a.cur_sum + b.mn < 0){
		ans.cur_sum = b.cur_sum - b.mn;
	}
	ans.mn = min(a.mn, a.cur_sum + b.mn);
	ans.mn = max(-cap, ans.mn);
	ans.mx = max(a.mx, a.cur_sum + b.mx);
	ans.mx = min(ans.mx, cap);
	return ans;
}

struct node{
	int s, e, m;
	dat val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val.cur_sum = val.mx = val.mn = 0;
	}
	
	void upd(int p, ll v){
		if(s == e){
			v = min(v, cap);
			v = max(v, -cap);
			val.cur_sum = val.mx = val.mn = v;
		}
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = comb(l->val, r->val);
			//cout << s << ' ' << e << '\n';
			//cout << val.cur_sum << ' ' << val.mx << ' ' << val.mn << '\n';
		}
	}
}*root;

vector <pi> Q[300005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = (int)c.size(), q = (int)l.size();
    cap = c[0];
    for(int i = 0; i < q; i++){
		Q[l[i]].push_back({i, v[i]});
		Q[r[i] + 1].push_back({i, 0});
	}
	root = new node(0, q - 1);
	vector <int> ans(n);
	for(int i = 0; i < n; i++){
		for(auto [a, b] : Q[i]){
			root->upd(a, b);
		}
		ans[i] = root->val.cur_sum;
	}
	return ans;
}

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