Submission #821899

#	Time	Username	Problem	Language	Result	Execution time	Memory
821899		TimDee	Distributing Candies (IOI21_candies)	C++17	100 / 100	2785 ms	36944 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second

#define int long long
const int inf=1e18;

const int sz = 1<<18;
int lazy[4*sz];
int mn[2*sz];
int mx[2*sz];

pi merge(pi a, pi b) {
	return {min(a.f,b.f), max(a.s,b.s)};
}
void push(int v) {
	mn[v]+=lazy[v];
	mx[v]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[2*v+2]+=lazy[v];
	lazy[v]=0;
}
void add(int v, int l, int r, int lx, int rx, int x) {
	if (lazy[v]) push(v);
	if (rx<=l || r<=lx) return;
	if (lx<=l && r<=rx) {
		lazy[v]+=x;
		push(v);
		return;
	}
	int m=(l+r)>>1;
	add(2*v+1,l,m,lx,rx,x);
	add(2*v+2,m,r,lx,rx,x);
	mn[v]=min(mn[2*v+1],mn[2*v+2]);
	mx[v]=max(mx[2*v+1],mx[2*v+2]);
}
void add(int l, int r, int x) {
	add(0,0,sz,l,r,x);
}
pi query(int v, int l, int r, int lx, int rx) {
	if (lazy[v]) push(v);
	if (rx<=l || r<=lx) return {inf,-inf};
	if (lx<=l && r<=rx) return {mn[v],mx[v]};
	int m=(l+r)>>1;
	auto lq=query(2*v+1,l,m,lx,rx);
	auto rq=query(2*v+2,m,r,lx,rx);
	mn[v]=min(mn[2*v+1],mn[2*v+2]);
	mx[v]=max(mx[2*v+1],mx[2*v+2]);
	return {min(lq.f,rq.f),max(lq.s,rq.s)};
}
pi query(int l, int r) {
	return query(0,0,sz,l,r);
}

#undef int

void addqueries(int n, vector<int>&l, vector<int>&r, vector<int>&v) {
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
	forn(i,2) l.pb(0);
	forn(i,2) r.pb(n-1);
	v.pb(-1e9); v.pb(1e9);
	reverse(all(l));
	reverse(all(r));
	reverse(all(v));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n=c.size(), q=l.size()+2;
	addqueries(n,l,r,v);

	vector<vector<int>> toadd(n), del(n);
	forn(i,q) toadd[l[i]].pb(i), del[r[i]].pb(i);

	vector<int> ans(n);
	forn(i,n) {
		for(auto&x:toadd[i]) add(x,q,v[x]);

		int l=0, r=q-1;
		while (l<r) {
			int mid=(l+r+1)>>1;
			auto x = query(mid,q);
			if (x.s - x.f < c[i]) r=mid-1;
			else l=mid;
		}
		auto z = query(r,q);
		int t=r;
		l=r+1, r=q-1;
		while (l<r) {
			int mid=(l+r)>>1;
			auto x=query(t+1,mid+1);
			if (x.s!=z.s && x.f!=z.f) l=mid+1;
			else r=mid;
		}
		auto x = query(r,r+1);
		auto y = query(q-1,q);
		z = query(t,t+1);
		if (x.f <= z.f) ans[i]=y.f-x.f;
		else ans[i]=c[i]+y.f-x.f;		

		for(auto&x:del[i]) add(x,q,-v[x]);
	}
	return ans;
}

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