Submission #897003

#	Time	Username	Problem	Language	Result	Execution time	Memory
897003		Faisal_Saqib	Distributing Candies (IOI21_candies)	C++17	100 / 100	511 ms	50968 KiB

candies

#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;
#define ll long long
const ll inf=1e18;
const ll N=2e5+3;
int qp;
vector<pair<int,int>> T[N];
struct Data
{
    ll sum=0;
    ll mi=0;
    ll mx=0;
    ll lazy=0;
};
Data idendity{0,inf,-inf,0};
Data join(Data l,Data r)
{
    return Data{l.sum+r.sum,min(l.mi,r.mi),max(l.mx,r.mx),0};
}
struct SegmentTree
{
    Data val;
    int s,e;
    SegmentTree* next[2];
    SegmentTree(int l,int r)
    {
        s=l;
        e=r;
        if(s!=e)
        {
            int mid=(s+e)/2;
            next[0]=new SegmentTree(s,mid);
            next[1]=new SegmentTree(mid+1,e);
        }
    }
    void push()
    {
        val.sum+=(e-s+1)*val.lazy;
        val.mi+=val.lazy;
        val.mx+=val.lazy;
        if(s!=e)
        {
            next[0]->val.lazy+=val.lazy;
            next[1]->val.lazy+=val.lazy;
        }
        val.lazy=0;
    }
    void pull()
    {        
        val=join(next[0]->val,next[1]->val);
    }
    void Update(int l,int r,ll v)
    {
        push();
        if(r<s or e<l)
            return;
        if(l<=s and e<=r)
        {
            val.lazy+=v;
            push();
            return;
        }
        next[0]->Update(l,r,v);
        next[1]->Update(l,r,v);
        pull();
    }
    int Just(ll al,ll mx=-inf,ll mi=inf) // al == ci , [s, e] -> s
    {
        if(s==e)
        {
             return s;
        }
        else
        {
            next[1]->push();
            next[0]->push();
            ll nmx=max(mx,next[1]->val.mx);
            ll nmi=min(mi,next[1]->val.mi);
            if((nmx-nmi)>=al)
            {
                // answer is in the range
                return next[1]->Just(al, mx, mi);
            }
            else
            {
                return next[0]->Just(al,nmx,nmi);
            }
        }
    }
    Data get(int l,int r=qp)
    {
        push();
        if(r<s or e<l)
            return idendity;
        if(l<=s and e<=r)
            return val;
        return join(next[0]->get(l),next[1]->get(l));
    }
};
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 q=l.size();
    qp=q;
    SegmentTree* st=new SegmentTree(0,qp);
    for(int i=0;i<q;i++)
    {
        T[l[i]].push_back({v[i],i+1});
        T[r[i]+1].push_back({-v[i],i+1});
    }
    vector<int> ans(n);
    ll tpot=0;
    for(int j=0;j<n;j++)
    {
        for(auto fi:T[j])
        {
            tpot+=fi.first;
            st->Update(fi.second,qp,fi.first);
        }
        long long cp=c[j];
        Data curap=st->get(0);
        if((curap.mx-curap.mi)<=cp)
        {
            ans[j]=(tpot-curap.mi);
            continue;
        }
        int s=st->Just(cp);
        curap=st->get(s);
        auto lpa=curap;
        curap=st->get(s+1) ;
        if(lpa.mx==curap.mx)
            ans[j]=tpot-lpa.mx+cp;
        else
            ans[j]=tpot-lpa.mi;
    }
    return ans;
}

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