Submission #500718

#	Time	Username	Problem	Language	Result	Execution time	Memory
500718		kderylo	Distributing Candies (IOI21_candies)	C++17	0 / 100	1059 ms	52700 KiB

candies

#include <iostream>
#include <vector>
using namespace std;
const int stala=262144;
long long tree[5*stala];
long long tree2[5*stala];
long long Tree[5*stala];
long long Tree2[5*stala];
int index[5*stala];
int index2[5*stala];
int maks_index=0;
vector<pair<int,long long> >poczatek[stala]; //czas wartosc
vector<pair<int,long long> >koniec[stala]; //czas wartosc
vector<int>wyjscie;
void update_max(int index,int index2,long long war,long long w[],long long W[],int ind[])
{
    index=index+stala-1;
    index2=index2+stala-1;
    w[index]+=war;
    if(index!=index2)
    {
        w[index2]+=war;
    }
    while(index>0)
    {
        if(index/2!=index2/2)
        {
            if(index%2==0)
            {
                w[index+1]+=war;
                W[index+1]=w[index+1]+max(W[2*(index+1)],W[(2*(index+1))+1]);
                if(index<stala)
                {
                    ind[index+1]=(W[2*(index+1)]>W[(2*(index+1))+1]) ? ind[2*(index+1)]:ind[(2*(index+1))+1];
                }
            }
            if(index2%2==1)
            {
                w[index2-1]+=war;
                W[index2-1]=w[index2-1]+max(W[2*(index2-1)],W[(2*(index2-1))+1]);
                if(index2<stala)
                {
                    ind[index2-1]=(W[2*(index2-1)]>W[(2*(index2-1))+1]) ? ind[2*(index2-1)]:ind[(2*(index2-1))+1];
                }
            }
        }
        W[index]=w[index]+max(W[2*index],W[(2*index)+1]);
        W[index2]=w[index2]+max(W[2*index2],W[(2*index2)+1]);
        if(index<stala)
        {
            ind[index]=(W[2*index]>W[(2*index)+1]) ? ind[2*index]:ind[(2*index)+1];
        }
        if(index2<stala)
        {
            ind[index2]=(W[2*index2]>W[(2*index2)+1]) ? ind[2*index2]:ind[(2*index2)+1];
        }
        index=index/2;
        index2=index2/2;
    }
}
long long query_max(int index,int index2,long long w[],long long W[],int ind[])
{
    maks_index=0;
    index=index+stala-1;
    index2=index2+stala-1;
    if(index==0)
    {
        return 0;
    }
    long long resp=0;
    long long resl=0;
    int indp=ind[index2];
    int indl=ind[index];
    while(index>0)
    {
        resl+=w[index];
        resp+=w[index2];
        if((index/2)!=(index2/2))
        {
            if(index%2==0)
            {
                indl=(resl>W[index+1]) ? indl:ind[index+1];
                resl=max(resl,W[index+1]);
            }
            if(index2%2==1)
            {
                indp=(resp>W[index2-1]) ? indp:ind[index2-1];
                resp=max(resp,W[index2-1]);
            }
        }
        index=index/2;
        index2=index2/2;
    }
    maks_index=(resp>resl) ? indp:indl;
    return max(resp,resl);
}
void update_min(int index,int index2,long long war,long long w[],long long W[],int ind[])
{
    index=index+stala-1;
    index2=index2+stala-1;
    w[index]+=war;
    if(index!=index2)
    {
        w[index2]+=war;
    }
    while(index>0)
    {
        if(index/2!=index2/2)
        {
            if(index%2==0)
            {
                w[index+1]+=war;
                W[index+1]=w[index+1]+min(W[2*(index+1)],W[(2*(index+1))+1]);
                if(index<stala)
                {
                    ind[index+1]=(W[2*(index+1)]<W[(2*(index+1))+1]) ? ind[2*(index+1)]:ind[(2*(index+1))+1];
                }
            }
            if(index2%2==1)
            {
                w[index2-1]+=war;
                W[index2-1]=w[index2-1]+min(W[2*(index2-1)],W[(2*(index2-1))+1]);
                if(index2<stala)
                {
                    ind[index2-1]=(W[2*(index2-1)]<W[(2*(index2-1))+1]) ? ind[2*(index2-1)]:ind[(2*(index2-1))+1];
                }
            }
        }
        W[index]=w[index]+min(W[2*index],W[(2*index)+1]);
        W[index2]=w[index2]+min(W[2*index2],W[(2*index2)+1]);
        if(index<stala)
        {
            ind[index]=(W[2*index]<W[(2*index)+1]) ? ind[2*index]:ind[(2*index)+1];
        }
        if(index2<stala)
        {
            ind[index2]=(W[2*index2]<W[(2*index2)+1]) ? ind[2*index2]:ind[(2*index2)+1];
        }
        index=index/2;
        index2=index2/2;
    }
}
long long query_min(int index,int index2,long long w[],long long W[],int ind[])
{
    maks_index=0;
    index=index+stala-1;
    index2=index2+stala-1;
    long long resp=0;
    long long resl=0;
    int indp=ind[index2];
    int indl=ind[index];
    while(index>0)
    {
        resl+=w[index];
        resp+=w[index2];
        if((index/2)!=(index2/2))
        {
            if(index%2==0)
            {
                indl=(resl<W[index+1]) ? indl:ind[index+1];
                resl=min(resl,W[index+1]);
            }
            if(index2%2==1)
            {
                indp=(resp<W[index2-1]) ? indp:ind[index2-1];
                resp=min(resp,W[index2-1]);
            }
        }
        index=index/2;
        index2=index2/2;
    }
    maks_index=(resp<resl) ? indp:indl;
    return min(resp,resl);
}
void pre()
{
    for(int i=stala;i<2*stala;i++)
    {
        index[i]=i-stala+1;
        index2[i]=i-stala+1;
    }
    for(int i=stala-1;i>=1;i--)
    {
        index[i]=index[2*i];
        index2[i]=index2[2*i];
    }
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v)
{
    pre();
    int czas=(int)l.size();
    for(int i=0; i<(int)l.size(); i++)
    {
        poczatek[l[i]].push_back(make_pair(i+1,v[i]));
        koniec[r[i]].push_back(make_pair(i+1,-v[i]));
    }
    for(int i=0; i<(int)c.size(); i++)
    {
        for(int j=0; j<(int)poczatek[i].size(); j++)
        {
            update_max(poczatek[i][j].first,czas,poczatek[i][j].second,tree,Tree,index);
            update_min(poczatek[i][j].first,czas,poczatek[i][j].second,tree2,Tree2,index2);
        }
        int pocz=1;
        int kon=czas;
        while (pocz < kon)
        {
            int srodek = (pocz + kon) / 2;
            if (query_max(srodek,czas,tree,Tree,index)-query_min(srodek,czas,tree2,Tree2,index2)<=c[i])
                kon = srodek;
            else
                pocz = srodek + 1;
        }
        query_min(pocz,czas,tree2,Tree2,index2);
        long long in=maks_index;
        query_max(pocz,czas,tree,Tree,index);
        long long in2=maks_index;
        if(in<in2)
        {
            in=query_min(in,in,tree2,Tree2,index2);
        }
        else if(in==in2&&query_max(in-1,in-1,tree,Tree,index)>query_max(in,in,tree,Tree,index))
        {
            in=query_min(in,in,tree2,Tree2,index2);
        }
        else
        {
            in=query_max(in2,in2,tree,Tree,index)-c[i];
        }
        long long pom=query_max(czas,czas,tree,Tree,index);
        wyjscie.push_back(pom-in);
        for(int j=0; j<(int)koniec[i].size(); j++)
        {
            update_max(koniec[i][j].first,czas,koniec[i][j].second,tree,Tree,index);
            update_min(koniec[i][j].first,czas,koniec[i][j].second,tree2,Tree2,index2);
        }
    }
    return wyjscie;
}

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