oj.uz

Submission #500835

# Submission time Handle Problem Language Result Execution time Memory
500835 2022-01-01T11:44:34 Z kderylo Distributing Candies (IOI21_candies) C++17
100 / 100
 1105 ms 50412 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=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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12748 KB Output is correct
2 Correct 6 ms 12748 KB Output is correct
3 Correct 11 ms 13008 KB Output is correct
4 Correct 8 ms 13052 KB Output is correct
5 Correct 11 ms 13132 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 44376 KB Output is correct
2 Correct 1105 ms 44340 KB Output is correct
3 Correct 1042 ms 44124 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 271 ms 43756 KB Output is correct
3 Correct 325 ms 19616 KB Output is correct
4 Correct 904 ms 49812 KB Output is correct
5 Correct 937 ms 50036 KB Output is correct
6 Correct 800 ms 50412 KB Output is correct
7 Correct 751 ms 49712 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12740 KB Output is correct
2 Correct 7 ms 12748 KB Output is correct
3 Correct 178 ms 36888 KB Output is correct
4 Correct 252 ms 17592 KB Output is correct
5 Correct 698 ms 43080 KB Output is correct
6 Correct 670 ms 43876 KB Output is correct
7 Correct 604 ms 44496 KB Output is correct
8 Correct 671 ms 43212 KB Output is correct
9 Correct 658 ms 44692 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12748 KB Output is correct
2 Correct 6 ms 12748 KB Output is correct
3 Correct 11 ms 13008 KB Output is correct
4 Correct 8 ms 13052 KB Output is correct
5 Correct 11 ms 13132 KB Output is correct
6 Correct 940 ms 44376 KB Output is correct
7 Correct 1105 ms 44340 KB Output is correct
8 Correct 1042 ms 44124 KB Output is correct
9 Correct 7 ms 12748 KB Output is correct
10 Correct 271 ms 43756 KB Output is correct
11 Correct 325 ms 19616 KB Output is correct
12 Correct 904 ms 49812 KB Output is correct
13 Correct 937 ms 50036 KB Output is correct
14 Correct 800 ms 50412 KB Output is correct
15 Correct 751 ms 49712 KB Output is correct
16 Correct 7 ms 12740 KB Output is correct
17 Correct 7 ms 12748 KB Output is correct
18 Correct 178 ms 36888 KB Output is correct
19 Correct 252 ms 17592 KB Output is correct
20 Correct 698 ms 43080 KB Output is correct
21 Correct 670 ms 43876 KB Output is correct
22 Correct 604 ms 44496 KB Output is correct
23 Correct 671 ms 43212 KB Output is correct
24 Correct 658 ms 44692 KB Output is correct
25 Correct 6 ms 12724 KB Output is correct
26 Correct 309 ms 17684 KB Output is correct
27 Correct 267 ms 43372 KB Output is correct
28 Correct 930 ms 48240 KB Output is correct
29 Correct 893 ms 48648 KB Output is correct
30 Correct 995 ms 48836 KB Output is correct
31 Correct 880 ms 49080 KB Output is correct
32 Correct 755 ms 49408 KB Output is correct