Submission #986417

#	Time	Username	Problem	Language	Result	Execution time	Memory
986417		Pyqe	Distributing Candies (IOI21_candies)	C++17	100 / 100	1177 ms	56260 KiB

candies

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,a[200069];
vector<pair<long long,long long>> ql[200069];

struct segtree
{
	long long l,r,mn,mx,lz;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		mn=0;
		mx=0;
		lz=0;
		if(l<r)
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	inline void blc()
	{
		long long ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mn+=lz;
			p[ii]->mx+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(long long lh,long long rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn+=w;
			mx+=w;
			lz+=w;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mn=min(p[0]->mn,p[1]->mn);
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	long long qrn(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mn;
		}
		else
		{
			blc();
			return min(p[0]->qrn(lh,rh),p[1]->qrn(lh,rh));
		}
	}
	long long qrx(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return -inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mx;
		}
		else
		{
			blc();
			return max(p[0]->qrx(lh,rh),p[1]->qrx(lh,rh));
		}
	}
}
sg;

vector<int> distribute_candies(vector<int> oa,vector<int> ka,vector<int> la,vector<int> wg)
{
	long long t,rr,i,j,k,l,w,sz,mn,mx,mn2,lh,rh,md,zz,z;
	vector<int> v;
	
	n=oa.size();
	for(i=1;i<=n;i++)
	{
		a[i]=oa[i-1];
	}
	t=ka.size();
	for(rr=1;rr<=t;rr++)
	{
		k=ka[rr-1]+1;
		l=la[rr-1]+1;
		w=wg[rr-1];
		ql[k].push_back({rr,w});
		ql[l+1].push_back({rr,-w});
	}
	sg.bd(0,t);
	for(i=1;i<=n;i++)
	{
		sz=ql[i].size();
		for(j=0;j<sz;j++)
		{
			k=ql[i][j].fr;
			w=ql[i][j].sc;
			sg.ud(k,t,w);
		}
		if(sg.mx-sg.mn<=a[i])
		{
			z=sg.qrn(t,t)-sg.mn;
		}
		else
		{
			for(lh=1,rh=t;lh<=rh;)
			{
				md=(lh+rh)/2;
				mn=sg.qrn(md,t);
				mx=sg.qrx(md,t);
				if(mx-mn<=a[i])
				{
					zz=md;
					rh=md-1;
				}
				else
				{
					lh=md+1;
				}
			}
			mn=sg.qrn(zz,t);
			mx=sg.qrx(zz,t);
			mn2=sg.qrn(zz-1,t);
			if(mn2<mn)
			{
				z=a[i]-(mx-sg.qrn(t,t));
			}
			else
			{
				z=sg.qrn(t,t)-mn;
			}
		}
		v.push_back(z);
	}
	return v;
}

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:89:10: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |   if(l>rh||r<lh)
      |      ~~~~^~~~~~
candies.cpp:108:49: note: 'zz' was declared here
  108 |  long long t,rr,i,j,k,l,w,sz,mn,mx,mn2,lh,rh,md,zz,z;
      |                                                 ^~

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