oj.uz

Submission #986417

# Submission time Handle Problem Language Result Execution time Memory
986417 2024-05-20T13:03:03 Z Pyqe Distributing Candies (IOI21_candies) C++17
100 / 100
 1177 ms 56260 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 3 ms 5464 KB Output is correct
4 Correct 3 ms 5464 KB Output is correct
5 Correct 5 ms 5468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 54528 KB Output is correct
2 Correct 1177 ms 53636 KB Output is correct
3 Correct 1057 ms 53424 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 229 ms 46036 KB Output is correct
3 Correct 245 ms 12728 KB Output is correct
4 Correct 1028 ms 55476 KB Output is correct
5 Correct 1032 ms 55848 KB Output is correct
6 Correct 1012 ms 56260 KB Output is correct
7 Correct 1068 ms 55528 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 108 ms 44580 KB Output is correct
4 Correct 200 ms 10948 KB Output is correct
5 Correct 603 ms 49936 KB Output is correct
6 Correct 691 ms 50196 KB Output is correct
7 Correct 778 ms 51064 KB Output is correct
8 Correct 607 ms 49500 KB Output is correct
9 Correct 812 ms 51304 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 3 ms 5464 KB Output is correct
4 Correct 3 ms 5464 KB Output is correct
5 Correct 5 ms 5468 KB Output is correct
6 Correct 1091 ms 54528 KB Output is correct
7 Correct 1177 ms 53636 KB Output is correct
8 Correct 1057 ms 53424 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 229 ms 46036 KB Output is correct
11 Correct 245 ms 12728 KB Output is correct
12 Correct 1028 ms 55476 KB Output is correct
13 Correct 1032 ms 55848 KB Output is correct
14 Correct 1012 ms 56260 KB Output is correct
15 Correct 1068 ms 55528 KB Output is correct
16 Correct 2 ms 4952 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 108 ms 44580 KB Output is correct
19 Correct 200 ms 10948 KB Output is correct
20 Correct 603 ms 49936 KB Output is correct
21 Correct 691 ms 50196 KB Output is correct
22 Correct 778 ms 51064 KB Output is correct
23 Correct 607 ms 49500 KB Output is correct
24 Correct 812 ms 51304 KB Output is correct
25 Correct 1 ms 4956 KB Output is correct
26 Correct 167 ms 11032 KB Output is correct
27 Correct 279 ms 45640 KB Output is correct
28 Correct 881 ms 53948 KB Output is correct
29 Correct 1032 ms 54416 KB Output is correct
30 Correct 1142 ms 54576 KB Output is correct
31 Correct 1111 ms 54800 KB Output is correct
32 Correct 1060 ms 55248 KB Output is correct