Submission #482976

#	Time	Username	Problem	Language	Result	Execution time	Memory
482976		MilosMilutinovic	Distributing Candies (IOI21_candies)	C++17	100 / 100	364 ms	49404 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
int n,q;
VI qs2[N];
vector<PII> qs[N];
ll pref4[N],mn[N],mx[N];
struct node{
	ll val,mn,mx;
	node() {mn=mx=val=0;}
}nd[4*N];
void upd(int p) {
	nd[p].val=nd[p*2].val+nd[p*2+1].val;
	nd[p].mn=min(nd[p*2].mn,nd[2*p].val+nd[p*2+1].mn);
	nd[p].mx=max(nd[p*2].mx,nd[2*p].val+nd[p*2+1].mx);
}
void modify(int p,int l,int r,int tl,int x) {
	if (l==r) {
		nd[p].val+=x;
		nd[p].mx=nd[p].val;
		nd[p].mn=nd[p].val;
	} else {
		int md=(l+r)>>1;
		if (tl<=md) modify(p*2,l,md,tl,x);
		else modify(p*2+1,md+1,r,tl,x);
		upd(p);
	}
}
int get(int p,int l,int r,int c) {
	if (l==r) return max(0LL,min((ll)c,nd[p].val));
	int md=(l+r)>>1;
	if (nd[p*2+1].mx-nd[p*2+1].mn>c) return get(p*2+1,md+1,r,c);
	int ret=get(p*2,l,md,c);
	if (ret+nd[2*p+1].mn<=0) return nd[p*2+1].val-nd[p*2+1].mn;
	if (ret+nd[2*p+1].mx>c) return c-(nd[p*2+1].mx-nd[p*2+1].val);
	return ret+nd[p*2+1].val;
}
VI distribute_candies(VI c,VI l,VI r,VI v) {
	n=SZ(c),q=SZ(v);
	VI a(n);
	rep(i,0,q) {
		qs[l[i]].pb(mp(i,v[i]));
		qs[r[i]+1].pb(mp(i,-v[i]));
	}
	rep(i,0,n) {
		for (auto x:qs[i]) modify(1,0,q-1,x.fi,x.se);
		a[i]=get(1,0,q-1,c[i]);
	}
	return a;
}

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