Submission #437087

#	Time	Username	Problem	Language	Result	Execution time	Memory
437087		nadidadit	Distributing Candies (IOI21_candies)	C++17	8 / 100	269 ms	14896 KiB

candies

#include "candies.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll cnt=0,cnt1=0,cnt2=0;
vector<ll>change;
ll mx=(ll)1e9+40;
void query(ll at,ll pos,ll l,ll r)
{
//	cout<<"l= "<<l<<" r= "<<r<<endl;
	if(pos<l || pos>r)
	{
		return;
	}
	if(pos>=l && pos<=r)
	{
		if(cnt<mx)
		{
		cnt+=change[at];
	    }
	    if(l==r)
	    {
	    	return;
		}
	//	cout<<"l= "<<l<<" r= "<<r<<" cnt= "<<cnt<<endl;
	}
	if(l==r)
	{
		return;
	}
	ll mid=(l+r)/2;
	query(at*2,pos,l,mid);
	query(at*2+1,pos,mid+1,r);
}
void update(ll at,ll L,ll R,ll l,ll r,ll u)
{
	cnt1++;
//	cout<<"at= "<<at<<" L= "<<L<<" R= "<<R<<" l= "<<l<<" r= "<<r<<endl;
	if(R<l || L>r)
	{
	//	cout<<"Hi"<<endl;
		return;
	}
//	cout<<"at= "<<at<<" L= "<<L<<" R= "<<R<<" l= "<<l<<" r= "<<r<<endl;
	if(l<=L && R<=r)
	{
	//	cout<<"L= "<<L<<" R= "<<R<<endl;
	    if(change[at]<mx)
	    {
			change[at]+=u;
	    }
		return;
	}
	if(L==R)
	{
		return;
	}
//	cout<<"Here"<<endl;
	ll mid=(L+R)/2;
	update(at*2,L,mid,l,r,u);
	update(at*2+1,mid+1,R,l,r,u);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
	int n=c.size();
	for(ll i=0;i<4*n+50;i++)
	{
		change.push_back((ll)0);
	}
    std::vector<int> s(n);
    ll x=l.size();
    for(ll i=0;i<n;i++)
    {
    	s[i]=0;
	}
//	cout<<"Hello"<<endl;
	for(ll i=0;i<x;i++)
	{
		cnt1=0;
//		cout<<"i= "<<i<<" l= "<<l[i]+1<<" r= "<<r[i]+1<<endl;
		update(1,1,n,l[i]+1,r[i]+1,v[i]);
//		cout<<"cnt1= "<<cnt1<<endl;
	}
	for(ll i=0;i<n;i++)
	{
		cnt=0;
		cnt2=0;
	//	cout<<"i= "<<i<<endl;
		query(1,i+1,1,n);
		//cout<<"cnt2= "<<cnt2<<endl;
		s[i]=min((ll)cnt,(ll)c[i]);
	}
    return s;
}
/*int main() {
	freopen("inputin.txt","r",stdin);
	freopen("testoutput.txt","w",stdout);
//	cout<<"Hi"<<endl;
    int n;
    cin>>n;
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        cin>>c[i];
    }

    int q;
    cin>>q;
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        scanf("%d %d %d", &l[i], &r[i], &v[i]);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
*/

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