Submission #435938

#	Time	Username	Problem	Language	Result	Execution time	Memory
435938		dqhungdl	Distributing Candies (IOI21_candies)	C++17	100 / 100	4608 ms	34896 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<long long,long long> ii;
const int MAX=200005;
const long long INF=1e18;
int n,m;
long long Pmin[4*MAX],Pmax[4*MAX],lazy[4*MAX];
vector<ii> events[MAX];

void down(int k) {
	Pmin[2*k]+=lazy[k],Pmin[2*k+1]+=lazy[k];
	Pmax[2*k]+=lazy[k],Pmax[2*k+1]+=lazy[k];
	lazy[2*k]+=lazy[k],lazy[2*k+1]+=lazy[k];
	lazy[k]=0;
}

void update(int k,int l,int r,int L,int R,int val) {
	if(l>R||L>r)
		return;
	if(L<=l&&r<=R) {
		Pmin[k]+=val;
		Pmax[k]+=val;
		lazy[k]+=val;
		return;
	}
	down(k);
	int mid=(l+r)/2;
	update(2*k,l,mid,L,R,val);
	update(2*k+1,mid+1,r,L,R,val);
	Pmin[k]=min(Pmin[2*k],Pmin[2*k+1]);
	Pmax[k]=max(Pmax[2*k],Pmax[2*k+1]);
}

void update(int limit,int val) {
	update(1,0,m,limit,m,val);
}

ii query(int k,int l,int r,int L,int R) {
	if(l>R||L>r)
		return {INF,-INF};
	if(L<=l&&r<=R)
		return {Pmin[k],Pmax[k]};
	down(k);
	int mid=(l+r)/2;
	ii p1=query(2*k,l,mid,L,R);
	ii p2=query(2*k+1,mid+1,r,L,R);
	return {min(p1.first,p2.first),max(p1.second,p2.second)};
}

long long queryPmin(int limit) {
	return query(1,0,m,limit,m).first;
}

long long queryPmax(int limit) {
	return query(1,0,m,limit,m).second;
}

long long queryPos(int pos) {
	return query(1,0,m,pos,pos).first;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=c.size(),m=v.size();
	for(int i=0;i<m;i++) {
		events[l[i]].push_back({i+1,v[i]});
		events[r[i]+1].push_back({i+1,-v[i]});
	}
	vector<int> rs(n);
	for(int i=0;i<n;i++) {
		// Update
		for(ii event:events[i])
			update(event.first,event.second);
		// If all updates are in range
		if(queryPmax(0)-queryPmin(0)<=c[i]) {
			int l=1,r=m,pivot=0;
			long long limit=queryPmin(0);
			while(l<=r) {
				int mid=(l+r)/2;
				if(queryPmin(mid)==limit) {
					l=mid+1;
					pivot=mid;
				}
				else
					r=mid-1;
			}
			rs[i]=queryPos(m)-queryPos(pivot);
			continue;
		}
		int l=0,r=m,pivot;
		while(l<=r) {
			int mid=(l+r)/2;
			if(queryPmax(mid)-queryPmin(mid)>c[i]) {
				pivot=mid;
				l=mid+1;
			} else
				r=mid-1;
		}
		// Find the last time touching the upper wall
		if(queryPmin(pivot)==queryPos(pivot)) {
			l=pivot+1,r=m;
			long long limit=queryPmax(pivot);
			while(l<=r) {
				int mid=(l+r)/2;
				if(queryPmax(mid)==limit) {
					pivot=mid;
					l=mid+1;
				} else
					r=mid-1;
			}
			rs[i]=c[i]+queryPos(m)-queryPos(pivot);
		} else { // Find the last time touching the lower wall
			l=pivot+1,r=m;
			long long limit=queryPmin(pivot);
			while(l<=r) {
				int mid=(l+r)/2;
				if(queryPmin(mid)==limit) {
					pivot=mid;
					l=mid+1;
				} else
					r=mid-1;
			}
			rs[i]=queryPos(m)-queryPos(pivot);
		}
	}
	return rs;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:104:5: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |    l=pivot+1,r=m;
      |    ~^~~~~~~~

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