Submission #824802

#	Time	Username	Problem	Language	Result	Execution time	Memory
824802		andrei_boaca	Distributing Candies (IOI21_candies)	C++17	11 / 100	92 ms	9784 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
int n,q;
vector<ll> v;
vector<int> sol;
ll s[200005];
vector<pll> ord;
ll sufmin[200005],sufmax[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> stanga,std::vector<int> dreapta, std::vector<int> vals)
{
    n = c.size();
    q=stanga.size();
    v.resize(n);
    sol.resize(n);
    if(n<=2000&&q<=2000)
    {
        for(int z=0;z<stanga.size();z++)
        {
            int l=stanga[z];
            int r=dreapta[z];
            int val=vals[z];
            for(int i=l;i<=r;i++)
            {
                v[i]+=val;
                if(v[i]<0)
                    v[i]=0;
                if(v[i]>c[i])
                    v[i]=c[i];
            }
        }
        for(int i=0;i<v.size();i++)
            sol[i]=v[i];
        return sol;
    }
    bool ok=1;
    for(int i=0;i<vals.size();i++)
        if(vals[i]<0)
            ok=0;
    if(ok)
    {
        for(int z=0;z<vals.size();z++)
        {
            int l=stanga[z];
            int r=dreapta[z];
            int val=vals[z];
            v[l]+=val;
            if(r+1<n)
                v[r+1]-=val;
        }
        ll suma=0;
        for(int i=0;i<n;i++)
        {
            suma+=v[i];
            sol[i]=min(suma,1LL*c[i]);
        }
        return sol;
    }
    ok=1;
    for(int i=0;i<vals.size();i++)
        if(stanga[i]!=0||dreapta[i]!=n-1)
            ok=0;
    if(ok)
    {
        for(int i=0;i<n;i++)
            ord.push_back({c[i],i});
        sort(ord.begin(),ord.end());
        for(int i=0;i<vals.size();i++)
            s[i+1]=vals[i];
        for(int i=1;i<=q;i++)
            s[i]=s[i-1]+s[i];
        sufmin[q]=q;
        sufmax[q]=q;
        for(int i=q-1;i>=1;i--)
        {
            sufmax[i]=sufmax[i+1];
            sufmin[i]=sufmin[i+1];
            if(s[i]>s[sufmax[i]])
                sufmax[i]=i;
            if(s[i]<s[sufmin[i]])
                sufmin[i]=i;
        }
        ll poz=0;
        if(s[sufmin[1]]<0)
            poz=sufmin[1];
        while(!ord.empty())
        {
            if(poz==q)
            {
                for(auto i:ord)
                    sol[i.second]=0;
                ord.clear();
                break;
            }
            ll p=sufmax[poz+1];
            ll val=s[p]-s[poz];
            while(!ord.empty()&&ord.back().first>=val)
            {
                ll i=ord.back().second;
                sol[i]=s[q]-s[poz];
                ord.pop_back();
            }
            if(p==q)
            {
                for(auto i:ord)
                    sol[i.second]=i.first;
                ord.clear();
                break;
            }
            while(!ord.empty())
            {
                ll i=ord.back().second;
                ll cc=ord.back().first;
                ll x=s[sufmin[p+1]]-(val-cc);
                if(x>=0)
                {
                    sol[i]=s[q]-s[poz]-(val-cc);
                    ord.pop_back();
                }
                else
                    break;
            }
            poz=sufmin[p];
        }
        return sol;
    }
    return sol;
}

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:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int z=0;z<stanga.size();z++)
      |                     ~^~~~~~~~~~~~~~
candies.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
candies.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
candies.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int z=0;z<vals.size();z++)
      |                     ~^~~~~~~~~~~~
candies.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
candies.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=0;i<vals.size();i++)
      |                     ~^~~~~~~~~~~~

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