oj.uz

Submission #500832

# Submission time Handle Problem Language Result Execution time Memory
500832 2022-01-01T11:21:42 Z kderylo Distributing Candies (IOI21_candies) C++17
8 / 100
 1087 ms 47924 KB 
#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=0;
        }
        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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12740 KB Output is correct
2 Incorrect 9 ms 12676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 46048 KB Output is correct
2 Correct 1079 ms 47924 KB Output is correct
3 Correct 1087 ms 47924 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 9 ms 12744 KB Output is correct
3 Incorrect 168 ms 39048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12740 KB Output is correct
2 Incorrect 9 ms 12676 KB Output isn't correct
3 Halted 0 ms 0 KB -