oj.uz

Submission #441661

# Submission time Handle Problem Language Result Execution time Memory
441661 2021-07-05T17:44:17 Z ogibogi2004 Distributing Candies (IOI21_candies) C++17
100 / 100
 764 ms 38212 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 8 ms 9636 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct
4 Correct 9 ms 9932 KB Output is correct
5 Correct 10 ms 9960 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 37260 KB Output is correct
2 Correct 736 ms 38100 KB Output is correct
3 Correct 737 ms 38212 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 222 ms 32488 KB Output is correct
3 Correct 196 ms 13700 KB Output is correct
4 Correct 764 ms 37256 KB Output is correct
5 Correct 667 ms 37536 KB Output is correct
6 Correct 546 ms 37416 KB Output is correct
7 Correct 553 ms 37512 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9696 KB Output is correct
3 Correct 148 ms 30264 KB Output is correct
4 Correct 128 ms 12516 KB Output is correct
5 Correct 436 ms 32680 KB Output is correct
6 Correct 415 ms 33544 KB Output is correct
7 Correct 337 ms 33548 KB Output is correct
8 Correct 501 ms 33548 KB Output is correct
9 Correct 569 ms 33540 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 8 ms 9636 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct
4 Correct 9 ms 9932 KB Output is correct
5 Correct 10 ms 9960 KB Output is correct
6 Correct 642 ms 37260 KB Output is correct
7 Correct 736 ms 38100 KB Output is correct
8 Correct 737 ms 38212 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 222 ms 32488 KB Output is correct
11 Correct 196 ms 13700 KB Output is correct
12 Correct 764 ms 37256 KB Output is correct
13 Correct 667 ms 37536 KB Output is correct
14 Correct 546 ms 37416 KB Output is correct
15 Correct 553 ms 37512 KB Output is correct
16 Correct 7 ms 9676 KB Output is correct
17 Correct 7 ms 9696 KB Output is correct
18 Correct 148 ms 30264 KB Output is correct
19 Correct 128 ms 12516 KB Output is correct
20 Correct 436 ms 32680 KB Output is correct
21 Correct 415 ms 33544 KB Output is correct
22 Correct 337 ms 33548 KB Output is correct
23 Correct 501 ms 33548 KB Output is correct
24 Correct 569 ms 33540 KB Output is correct
25 Correct 6 ms 9676 KB Output is correct
26 Correct 157 ms 12500 KB Output is correct
27 Correct 253 ms 32812 KB Output is correct
28 Correct 706 ms 37448 KB Output is correct
29 Correct 669 ms 37492 KB Output is correct
30 Correct 649 ms 37516 KB Output is correct
31 Correct 578 ms 37516 KB Output is correct
32 Correct 545 ms 37532 KB Output is correct