Submission #481145

#	Time	Username	Problem	Language	Result	Execution time	Memory
481145		rumen_m	Distributing Candies (IOI21_candies)	C++17	0 / 100	5092 ms	27272 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 2e6+2;
long long c[MAXN];
vector <int> ans;
struct Segment
{
    long long minel[MAXN],maxel[MAXN], lazy[MAXN];
    void update_lazy(long long v, long long from, long long to)
    {
        if(lazy[v]==0)return ;
        minel[2*v]+=lazy[v];
        maxel[2*v]+=lazy[v];
        minel[2*v+1]+=lazy[v];
        maxel[2*v+1]+=lazy[v];
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
        lazy[v] = 0;
    }
    void update(long long v,long long from, long long to, long long l, long long r, long long delta)
    {
          //  cout<<"UPDATE:: "<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<" "<<delta<<endl;
        if(from==to)
        {
            minel[v] = max((long long)0, min(c[from],minel[v]+delta));
            maxel[v] = max((long long)0, min(c[from],maxel[v]+delta));
        //    cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
            return ;
        }
         update_lazy(v,from,to);
         long long mid = (from+to)/2;
        if(l<=from&&to<=r)
        {
            minel[v]+=delta;
            maxel[v]+=delta;
            if(minel[v]<0||maxel[v]>c[0])
            {
                update(2*v,from,mid,l,r,delta);
                update(2*v+1,mid+1,to,l,r,delta);
                minel[v] = min(minel[2*v],minel[2*v+1]);
                maxel[v] = max(maxel[2*v],maxel[2*v+1]);
            }
            else
                lazy[v]+=delta;
            return ;
        }
        if(l<=mid)
        update(2*v,from,mid,l,r,delta);
        if(r>mid)
        update(2*v+1,mid+1,to,l,r,delta);
        minel[v] = min(minel[2*v],minel[2*v+1]);
                maxel[v] = max(maxel[2*v],maxel[2*v+1]);
               // cout<<v<<" "<<minel[v]<<" "<<maxel[v]<<endl;
    }
    void query(long long v, long long from, long long to)
    {
        if(from==to)
        {
         //  cout<<"-> "<<from<<" "<<minel[v]<<endl;
            ans[from] =  minel[v];
            return ;
        }
        long long mid = (from+to)/2;
        update_lazy(v,from,to);
        query(2*v,from,mid);
        query(2*v+1,mid+1,to);
    }
};
Segment S;
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();
    int i,j;
    for(i = 0; i<n;i++)
        c[i] = _c[i];
    for(i=0;i<l.size();i++)
    {
        S.update(1,0,n-1,l[i],r[i],v[i]);
    }
    ans.resize(n);
    S.query(1,0,n-1);
    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:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(i=0;i<l.size();i++)
      |             ~^~~~~~~~~
candies.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
   74 |     int i,j;
      |           ^

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