Submission #446125

#	Time	Username	Problem	Language	Result	Execution time	Memory
446125		dennisstar	Distributing Candies (IOI21_candies)	C++17	100 / 100	508 ms	37016 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 1<<19;

vector<ll> smx(MX), smn(MX), st(MX);

void upd(int i, int s, int e, int t, ll v) {
	if (s==e) {
		smx[i]=max(0ll, v);
		smn[i]=min(0ll, v);
		st[i]=v;
		return ;
	}

	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, v);
	else upd(i*2+1, m+1, e, t, v);
	
	st[i]=st[i*2]+st[i*2+1];
	smx[i]=max(smx[i*2], st[i*2]+smx[i*2+1]);
	smn[i]=min(smn[i*2], st[i*2]+smn[i*2+1]);
}

ll get(int i, int s, int e, ll c) {
	if (s==e) return min(max(st[i], 0ll), c);

	int m=(s+e)/2;
	if (smx[i*2+1]-smn[i*2+1]>c) return get(i*2+1, m+1, e, c);

	ll r=get(i*2, s, m, c);
	if (r+smx[i*2+1]>c) return c-(smx[i*2+1]-st[i*2+1]);
	if (r+smn[i*2+1]<0) return st[i*2+1]-smn[i*2+1];
	return r+st[i*2+1];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int N=c.size(), Q=l.size();
	vector<int> rt;

	vector<vector<int>> q(N+1);
	for (int i=0; i<Q; i++) q[l[i]].emplace_back(i+1), q[r[i]+1].emplace_back(-(i+1));
	for (int i=0; i<N; i++) {
		for (auto &j:q[i]) {
			if (j>0) j--, upd(1, 0, Q-1, j, v[j]);
			else j=-j-1, upd(1, 0, Q-1, j, 0);
		}
		rt.emplace_back(get(1, 0, Q-1, c[i]));
	}

	return rt;
}

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