Submission #441661

#	Time	Username	Problem	Language	Result	Execution time	Memory
441661		ogibogi2004	Distributing Candies (IOI21_candies)	C++17	100 / 100	764 ms	38212 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=1e9;
struct node
{
	ll maxval,minval,sum;
};
node merge(node n1,node n2)
{
	n1.maxval=max(n1.maxval,n1.sum+n2.maxval);
	n1.minval=min(n1.minval,n1.sum+n2.minval);
	n1.sum=n1.sum+n2.sum;
	return n1;
}
struct segment_tree
{
	node tree[4*MAXN];
	void build(int l,int r,int idx)
	{
		if(l==r)
		{
			tree[idx].maxval=0;
			tree[idx].minval=0;
			tree[idx].sum=0;
			return;
		}
		int mid=(l+r)/2;
		build(l,mid,idx*2);
		build(mid+1,r,idx*2+1);
		tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
	}
	void update(int l,int r,int idx,int q,int val)
	{
		if(l>q)return;
		if(r<q)return;
		if(l==r)
		{
			tree[idx].maxval=val;
			tree[idx].minval=val;
			tree[idx].sum=val;
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,idx*2,q,val);
		update(mid+1,r,idx*2+1,q,val);
		tree[idx]=merge(tree[idx*2],tree[idx*2+1]);
	}
	node query(int l,int r,int idx,int ql,int qr)
	{
		if(l>=ql&&r<=qr)return tree[idx];
		int mid=(l+r)/2;
		if(qr<=mid)return query(l,mid,idx*2,ql,qr);
		else if(ql>mid)return query(mid+1,r,idx*2+1,ql,qr);
		else return merge(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
}t;
struct update
{
	int when,v;
};
vector<update>ul[MAXN],ur[MAXN];
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    ll n = c.size(),q=l.size();
    vector<int>s(n,0);
    ul[0].push_back({1,+INF});
    ur[n-1].push_back({1,+INF});
    ul[0].push_back({2,-INF});
    ur[n-1].push_back({2,-INF});
    for(int i=0;i<q;i++)
    {
		ul[l[i]].push_back({i+3,v[i]});
		ur[r[i]].push_back({i+3,v[i]});
	}
	t.build(1,q+2,1);
	for(int idx=0;idx<n;idx++)
	{
		for(auto xd:ul[idx])
		{
			t.update(1,q+2,1,xd.when,xd.v);
		}
		int low=1,high=q+2,mid,ans;
		node rupert;
		while(low<=high)
		{
			mid=(low+high)/2;
			rupert=t.query(1,q+2,1,mid,q+2);
			if(rupert.maxval-rupert.minval>=c[idx])
			{
				ans=mid;
				low=mid+1;
			}
			else 
			{
				high=mid-1;
			}
		}
		rupert=t.query(1,q+2,1,ans,q+2);
		int minval=rupert.minval;
		int maxval=rupert.maxval;
		int sum=rupert.sum;
		//cout<<idx<<":\n";
		//cout<<minval<<" "<<maxval<<" "<<ans<<endl;
		rupert=t.query(1,q+2,1,ans,ans);
		//cout<<rupert.maxval<<endl;
		if(rupert.maxval==maxval)
		{
			s[idx]=sum-minval;
		}
		else
		{
			s[idx]=c[idx]-(maxval-sum);
		}
		for(auto xd:ur[idx])
		{
			t.update(1,q+2,1,xd.when,0);
		}
	}
	return s;
}

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:54:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if(l>=ql&&r<=qr)return tree[idx];
      |      ~^~~~
candies.cpp:86:26: note: 'ans' was declared here
   86 |   int low=1,high=q+2,mid,ans;
      |                          ^~~

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