Submission #705847

#	Time	Username	Problem	Language	Result	Execution time	Memory
705847		ToroTN	Distributing Candies (IOI21_candies)	C++17	100 / 100	1951 ms	42488 KiB

candies

#include<bits/stdc++.h>
using namespace std;
#include "candies.h"
//#include "grader.cpp"
#define pb push_back
#define X first
#define Y second
#define ll long long
ll mx[800005],mn[800005],lz[800005];
vector<pair<ll,ll> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(ll tree,ll st,ll ed)
{
    mx[tree]+=lz[tree],mn[tree]+=lz[tree];
    if(st!=ed)
    {
        lz[2*tree]+=lz[tree],lz[2*tree+1]+=lz[tree];
    }
    lz[tree]=0;
}
void update(ll tree,ll st,ll ed,ll l,ll r,ll val)
{
    ll md=(st+ed)/2;
    if(st>=l&&ed<=r)
    {
        lz[tree]+=val;
    }
    uptlz(tree,st,ed);
    if(st>r||ed<l)return;
    if(st>=l&&ed<=r)return;
    update(2*tree,st,md,l,r,val);
    update(2*tree+1,md+1,ed,l,r,val);
    mx[tree]=max(mx[2*tree],mx[2*tree+1]);
    mn[tree]=min(mn[2*tree],mn[2*tree+1]);
}
ll query_mx(ll tree,ll st,ll ed,ll l,ll r)
{
    ll md=(st+ed)/2;
    uptlz(tree,st,ed);
    if(st>r||ed<l)return -1e18;
    if(st>=l&&ed<=r)return mx[tree];
    return max(query_mx(2*tree,st,md,l,r),query_mx(2*tree+1,md+1,ed,l,r));
}
ll query_mn(ll tree,ll st,ll ed,ll l,ll r)
{
    ll md=(st+ed)/2;
    uptlz(tree,st,ed);
    if(st>r||ed<l)return 1e18;
    if(st>=l&&ed<=r)return mn[tree];
    return min(query_mn(2*tree,st,md,l,r),query_mn(2*tree+1,md+1,ed,l,r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    ll n = c.size();
    ll m=v.size();
    for(int i=0;i<m;i++)
    {
        sweep[l[i]+1].pb({i+1,v[i]});
        sweep[r[i]+2].pb({i+1,-v[i]});
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%d\n",i);
        for(int j=0;j<sweep[i].size();j++)
        {
            printf("%d %d\n",sweep[i][j].X,sweep[i][j].Y);
        }
        printf("\n");
    }*/
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<sweep[i].size();j++)
        {
            int cmd=sweep[i][j].X,flag=sweep[i][j].Y;
            update(1,1,m,cmd,m,flag);
        }
        /*printf("i=%d\n",i);
        for(int j=1;j<=m;j++)
        {
            printf("%lld ",query(1,1,m,j,j));
        }
        printf("\n");*/
        ll st=0,md,ed=m;
        while(ed>=st)
        {
            md=(st+ed)/2;
            ll diff;
            pair<ll,ll> rng={query_mx(1,1,m,md,m),query_mn(1,1,m,md,m)};
            if(md==0)
            {
                diff=query_mx(1,1,m,1,m);
            }else
            {
                diff=rng.X-rng.Y;
            }
            if(diff>c[i-1])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        ll fn=query_mx(1,1,m,m,m);//final poll
        ll l1,r1,l2,r2,base;
        if(ed==-1)
        {
            l1=min((ll)0,query_mn(1,1,m,1,m));
            r1=query_mx(1,1,m,1,m);
            ans.pb(fn-l1);
        }else 
        {
            if(ed==0)
            {
                l1=0;
                r1=query_mx(1,1,m,1,m);
            }else
            {
                l1=query_mn(1,1,m,ed,m);
                r1=query_mx(1,1,m,ed,m);
            }
            l2=query_mn(1,1,m,ed+1,m);
            r2=query_mx(1,1,m,ed+1,m);
            if(l1==l2)
            {
                base=l1;
            }else
            {
                base=r1-c[i-1];
            }
            ans.pb(fn-base);
        }
    }
    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:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j=0;j<sweep[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
candies.cpp:105:21: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
  105 |         ll l1,r1,l2,r2,base;
      |                     ^~

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