Submission #705812

#	Time	Username	Problem	Language	Result	Execution time	Memory
705812		ToroTN	Distributing Candies (IOI21_candies)	C++17	0 / 100	5062 ms	23584 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
int mx[800005],mn[800005],lz[800005];
vector<pair<int,int> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(int tree,int st,int 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(int tree,int st,int ed,int l,int r,int val)
{
    int 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]);
}
pair<int,int> query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    uptlz(tree,st,ed);
    if(st>r||ed<l)return {-1e9,1e9};
    if(st>=l&&ed<=r)return {mx[tree],mn[tree]};
    return {max(query(2*tree,st,md,l,r).X,query(2*tree+1,md+1,ed,l,r).X),min(query(2*tree,st,md,l,r).Y,query(2*tree+1,md+1,ed,l,r).Y)};
}
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(),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("%d ",query(1,1,m,j,j));
        }
        printf("\n");*/
        int st=0,md,ed=m;
        while(ed>=st)
        {
            md=(st+ed)/2;
            int diff;
            if(md==0)
            {
                diff=query(1,1,m,1,m).X;
            }else
            {
                diff=query(1,1,m,md,m).X-query(1,1,m,md,m).Y;
            }
            if(diff>c[i-1])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        int fn=query(1,1,m,m,m).X;//final point
        int l1,r1,l2,r2,base;
        if(ed==-1)
        {
            l1=min(0,query(1,1,m,1,m).Y);
            r1=query(1,1,m,1,m).X;
            ans.pb(fn-l1);
        }else 
        {
            if(ed==0)
            {
                l1=0;
                r1=query(1,1,m,1,m).X;
            }else
            {
                l1=query(1,1,m,ed,m).Y;
                r1=query(1,1,m,ed,m).X;
            }
            l2=query(1,1,m,ed+1,m).Y;
            r2=query(1,1,m,ed+1,m).X;
            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:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j=0;j<sweep[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
candies.cpp:94:22: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
   94 |         int l1,r1,l2,r2,base;
      |                      ^~

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