Submission #1203663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203663		simona1230	Distributing Candies (IOI21_candies)	C++17	8 / 100	1261 ms	51924 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=2*1e5+5;
struct upd
{
    long long l,r,v,i;
    upd(){}
    upd(long long _l,long long _r,long long _v,long long _i)
    {
        l=_l;
        r=_r;
        v=_v;
        i=_i;
    }

    bool operator<(const upd&u)const
    {
        return l<u.l;
    }
};

struct segm
{
    long long maxx,minn,maxi,mini,sum;
    segm(){}
    segm(long long x,long long n,long long xi,long long ni,long long s)
    {
        maxx=x;
        minn=n;
        maxi=xi;
        mini=ni;
        sum=s;
    }
};

segm t[4*maxn];

void init(long long i,long long l,long long r)
{
    if(l==r)
    {
        t[i].maxi=t[i].mini=l;
        return;
    }
    long long m=(l+r)/2;
    init(i*2,l,m);
    init(i*2+1,m+1,r);
    t[i].maxi=t[i].mini=l;
}

segm pull(segm s1,segm s2)
{
    segm s={0,0,0,0,0};
    if(s1.maxx>s2.maxx)
    {
        s.maxx=s1.maxx;
        s.maxi=s1.maxi;
    }
    else
    {
        s.maxx=s2.maxx;
        s.maxi=s2.maxi;
    }

    if(s1.minn<s2.minn)
    {
        s.minn=s1.minn;
        s.mini=s1.mini;
    }
    else
    {
        s.minn=s2.minn;
        s.mini=s2.mini;
    }

    s.sum=s1.sum+s2.sum;
    return s;
}
long long lz[4*maxn];

void push(long long i,long long l,long long r)
{
    t[i].minn+=lz[i];
    t[i].maxx+=lz[i];
    t[i].sum+=(r-l+1)*lz[i];

    if(l!=r)
    {
        lz[i*2]+=lz[i];
        lz[i*2+1]+=lz[i];
    }

    lz[i]=0;
}

void update(long long i,long long l,long long r,long long ql,long long qr,long long x)
{
    push(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        lz[i]+=x;
        push(i,l,r);
        return;
    }
    long long m=(l+r)/2;
    update(i*2,l,m,ql,min(qr,m),x);
    update(i*2+1,m+1,r,max(m+1,ql),qr,x);

    t[i]=pull(t[i*2],t[i*2+1]);
}

segm query(long long i,long long l,long long r,long long ql,long long qr)
{
    push(i,l,r);
    if(ql>qr)return {(long long)-1e18,(long long)1e18,0,0,0};
    if(ql<=l&&r<=qr)return t[i];
    long long m=(l+r)/2;
    return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}


upd u[maxn];
vector<upd> q[maxn];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    for(long long i=0;i<l.size();i++)
        u[i]={l[i],r[i],v[i],i};
    sort(u,u+l.size());

    vector<int> ans(c.size());
    init(1,0,l.size());

    long long j=0;
    long long sum=0;
    for(long long i=0;i<c.size();i++)
    {
        while(j<l.size()&&u[j].l==i)
        {
            //cout<<"+ "<<u[j].i<<" "<<j<<endl;
            sum+=u[j].v;
            update(1,0,l.size()-1,u[j].i,c.size()-1,u[j].v);
            q[u[j].r+1].push_back(u[j]);
            j++;
        }

        for(long long j=0;j<q[i].size();j++)
        {
            //cout<<"- "<<q[i][j].i<<endl;
            sum-=q[i][j].v;
            update(1,0,l.size()-1,q[i][j].i,c.size()-1,-q[i][j].v);
        }

        long long wall=-1,tp=0;
        long long lf=0,rt=c.size()-1;
        while(lf<=rt)
        {
            long long m=(lf+rt)/2;
            segm s=query(1,0,l.size()-1,m,c.size()-1);
            //cout<<m<<": "<<s.minn<<" "<<s.maxx<<" "<<s.mini<<" "<<s.maxi<<endl;
            if(s.maxx-s.minn>=c[i])
            {
                //cout<<"in "<<endl;
                if(s.maxi>s.mini)wall=s.maxi,tp=1;
                else wall=s.mini,tp=0;
                lf=m+1;
            }
            else rt=m-1;
        }
        //cout<<sum<<endl;

        if(wall==-1)
        {
            wall=0;
            segm s=query(1,0,l.size()-1,0,l.size()-1);
            if(s.minn<0&&-s.minn>=c[i])wall=s.minn;
            if(s.maxx>0&&s.maxx>=c[i])wall=s.maxx-c[i];
            ans[i]=sum-wall;
            continue;
        }

        wall=query(1,0,l.size(),wall,wall).sum;
        if(tp==1)wall-=c[i];
        //cout<<wall<<endl;
        ans[i]=sum-wall;
        //cout<<i<<" "<<sum<<" "<<wall<<endl;
    }

    return ans;
}

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