Submission #469251

#	Time	Username	Problem	Language	Result	Execution time	Memory
469251		kderylo	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2096 ms	406880 KiB

prison

#include <iostream>
#include <vector>
using namespace std;
const int stala=2097152;
int tab[stala];
int przedzial[stala];
vector<int>wektor;
vector<int>wektor2;
vector<int>tree[2*stala];
bool odwiedzony[stala];
vector<int>lista;
int w[4*stala];
int W[4*stala];
int ind[4*stala];
int maks_index;
void update(int index,int index2,int war)
{
    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;
    }
}
int query(int index,int index2)
{
    maks_index=0;
    index=index+stala-1;
    index2=index2+stala-1;
    int resp=0;
    int 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 pre()
{
    for(int i=stala;i<2*stala;i++)
    {
        ind[i]=i-stala+1;
    }
    for(int i=stala-1;i>=1;i--)
    {
        ind[i]=ind[2*i];
    }
}
void update2(int x1,int x2,int index)
{
    x1+=stala-1;
    x2+=stala-1;
    tree[x1].push_back(index);
    if(x1!=x2)
    {
        tree[x2].push_back(index);
    }
    while(x1/2!=x2/2)
    {
        if(x1%2==0)
        {
            tree[x1+1].push_back(index);
        }
        if(x2%2==1)
        {
            tree[x2-1].push_back(index);
        }
        x1/=2;
        x2/=2;
    }
}
void query2(int x1)
{
    x1+=stala-1;
    while(x1>0)
    {
        for(int i=0;i<(int)tree[x1].size();i++)
        {
            if(odwiedzony[tree[x1][i]]==0)
            {
                odwiedzony[tree[x1][i]]=1;
                lista.push_back(tree[x1][i]);
            }
        }
        tree[x1].clear();
        x1/=2;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,materace,t;
    cin>>ile>>materace>>t;
    for(int i=1;i<=ile;i++)
    {
        cin>>tab[i];
    }
    for(int i=1;i<=ile;i++)
    {
        if(tab[i]<=t)
        {
            int index=min(ile,t-tab[i]+i);
            while(!wektor.empty()&&wektor.back()<=index)
            {
                wektor.pop_back();
                wektor2.pop_back();
            }
            wektor.push_back(index);
            wektor2.push_back(i);
            przedzial[i]=i;
        }
        else if(!wektor.empty())
        {
            przedzial[i]=wektor2.back();
        }
        else
        {
            przedzial[i]=-1;
        }
        if(!wektor.empty())
        {
            if(wektor.back()==i)
            {
                wektor.pop_back();
                wektor2.pop_back();
            }
        }
    }
    pre();
    int nie=0;
    for(int i=1;i<=ile;i++)
    {
        if(przedzial[i]==-1)
        {
            nie++;
        }
        else if(przedzial[i]<i)
        {
            update(przedzial[i],i-1,1);
            update2(przedzial[i],i-1,i);
        }
    }
    for(int i=1;i<=materace;i++)
    {
        nie+=query(1,ile);
        query2(maks_index);
        for(int j=0;j<(int)lista.size();j++)
        {
            int p=lista[j];
            update(przedzial[p],p-1,-1);
        }
        lista.clear();
    }
    cout<<ile-nie;

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20