Submission #500835

#	Time	Username	Problem	Language	Result	Execution time	Memory
500835		kderylo	Distributing Candies (IOI21_candies)	C++17	100 / 100	1105 ms	50412 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];
vector<pair<int,long long> >poczatek[stala]; //czas wartosc
vector<pair<int,long long> >koniec[stala]; //czas wartosc
vector<int>wyjscie;

int tab[stala];
void update_max(int index,int index2,long long war,long long w[],long long W[])
{
    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(index2%2==1)
            {
                w[index2-1]+=war;
                W[index2-1]=w[index2-1]+max(W[2*(index2-1)],W[(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]);
        index=index/2;
        index2=index2/2;
    }
}
long long query_max(int index,int index2,long long w[],long long W[])
{
    index=index+stala-1;
    index2=index2+stala-1;
    long long resp=0;
    long long resl=0;
    while(index>0)
    {
        resl+=w[index];
        resp+=w[index2];
        if((index/2)!=(index2/2))
        {
            if(index%2==0)
            {
                resl=max(resl,W[index+1]);
            }
            if(index2%2==1)
            {
                resp=max(resp,W[index2-1]);
            }
        }
        index=index/2;
        index2=index2/2;
    }
    return max(resp,resl);
}
void update_min(int index,int index2,long long war,long long w[],long long W[])
{
    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(index2%2==1)
            {
                w[index2-1]+=war;
                W[index2-1]=w[index2-1]+min(W[2*(index2-1)],W[(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]);
        index=index/2;
        index2=index2/2;
    }
}
long long query_min(int index,int index2,long long w[],long long W[])
{
    index=index+stala-1;
    index2=index2+stala-1;
    long long resp=0;
    long long resl=0;
    while(index>0)
    {
        resl+=w[index];
        resp+=w[index2];
        if((index/2)!=(index2/2))
        {
            if(index%2==0)
            {
                resl=min(resl,W[index+1]);
            }
            if(index2%2==1)
            {
                resp=min(resp,W[index2-1]);
            }
        }
        index=index/2;
        index2=index2/2;
    }
    return min(resp,resl);
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v)
{
    int czas=(int)l.size()+1;
    for(int i=0; i<(int)l.size(); i++)
    {
        poczatek[l[i]].push_back(make_pair(i+2,v[i]));
        koniec[r[i]].push_back(make_pair(i+2,-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);
            update_min(poczatek[i][j].first,czas,poczatek[i][j].second,tree2,Tree2);
        }
        int pocz=1;
        int kon=czas;
        while (pocz < kon)
        {
            int srodek = (pocz + kon) / 2;
            if (query_max(srodek,czas,tree,Tree)-query_min(srodek,czas,tree2,Tree2)<=c[i])
                kon = srodek;
            else
                pocz = srodek + 1;
        }
        long long minimum=query_min(pocz,czas,tree2,Tree2);
        long long maksimum=query_max(pocz,czas,tree,Tree);
        long long dol;
        if(pocz==1)
        {
            dol=minimum;
        }
        else if(query_max(pocz-1,pocz-1,tree,Tree)<minimum)
        {
            dol=maksimum-c[i];
        }
        else
        {
            dol=minimum;
        }
        long long pom=query_max(czas,czas,tree,Tree);
        wyjscie.push_back(pom-dol);
        for(int j=0; j<(int)koniec[i].size(); j++)
        {
            update_max(koniec[i][j].first,czas,koniec[i][j].second,tree,Tree);
            update_min(koniec[i][j].first,czas,koniec[i][j].second,tree2,Tree2);
        }
    }
    return wyjscie;
}

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