Submission #894795

#	Time	Username	Problem	Language	Result	Execution time	Memory
894795		Muhammad_Aneeq	Distributing Candies (IOI21_candies)	C++17	0 / 100	94 ms	14940 KiB

candies

#include <vector>
using namespace std;
int const N=2e5+10;
struct segt
{
    int lazy=0,sp=0,fi=0;
};
segt St[4*N]={};
int a[N]={};
void build(int i,int st,int en)
{
    if (st==en)
    {
        St[i].sp=a[st];
        St[i].fi=0;
        return;
    }
    int mid=(st+en)/2;
    build(i*2,st,mid);build(i*2+1,mid+1,en);
    St[i].sp=min(St[i*2].sp,St[i*2+1].sp);
    St[i].fi=max(St[i*2].fi,St[i*2+1].fi);
}
void update(int i,int st,int en,int l,int r,int val)
{
    if (st>r||en<l)
        return;
    if (St[i].sp==0&&val>0)
        return;
    if (St[i].fi==0&&val<0)
        return;
    if (st>=l&&en<=r&&St[i].sp-val>=0&&St[i].fi+val>=0)
    {
        St[i].sp+=val;
        St[i].fi+=val;
        St[i].lazy+=val;
        return;
    }
    if (st>=l&&en<=r&&st==en)
    {
        St[i].sp=min(a[st],max(St[i].sp-val,0));
        St[i].fi=min(a[st],max(St[i].sp+val,0));
        return;
    }
    int mid=(st+en)/2;
    update(i*2,st,mid,l,r,val+St[i].lazy);update(i*2+1,mid+1,en,l,r,val+St[i].lazy);
    St[i].lazy=0;
    St[i].sp=min(St[i*2].sp,St[i*2+1].sp);
    St[i].fi=max(St[i*2].fi,St[i*2+1].fi);
}
int get(int i,int st,int en,int r)
{
    if (st==en)
        return St[i].fi;
    int mid=(st+en)/2;
    if (r<=mid)
        return get(i*2,st,mid,r);
    return get(i*2+1,mid+1,en,r);
}
int n;
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v)
{
    n=c.size();
    for (int i=0;i<n;i++)
        a[i]=c[i];
    build(1,0,n-1);
    for (int i=0;i<l.size();i++)
        update(1,0,n-1,l[i],r[i],v[i]);
    update(1,0,n-1,0,n-1,0);
    vector<int>ans;
    for (int i=0;i<n;i++)
        ans.push_back(get(1,0,n-1,i));
    return ans;
}

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:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~

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