Submission #233919

#	Time	Username	Problem	Language	Result	Execution time	Memory
233919		Andrei_Cotor	Cake (CEOI14_cake)	C++11	100 / 100	374 ms	7444 KiB

cake

#include<iostream>
#include<algorithm>

using namespace std;

int Top10[15],A[250005],Coresp[250005]; //Coresp=cine imi scoate pozitia i (i<a). Pt update analizez ce se modifica la corespondenti
int Max[1000005],Lazy[1000005];

void build(int nod, int st, int dr)
{
    Lazy[nod]=-1;
    if(st==dr)
    {
        Max[nod]=Coresp[st];
        return;
    }
    
    int mij=(st+dr)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);

    Max[nod]=max(Max[2*nod],Max[2*nod+1]);
}

void propag(int nod, int st, int dr)
{
    if(Lazy[nod]==-1)
        return;

    Max[nod]=Lazy[nod];
    if(st!=dr)
    {
        Lazy[2*nod]=Lazy[nod];
        Lazy[2*nod+1]=Lazy[nod];
    }

    Lazy[nod]=-1;
}

int src(int nod, int st, int dr, int val) //>val
{
    if(st==dr)
    {
        if(Max[nod]<=val)
            return 0;
        return st;
    }

    int mij=(st+dr)/2;
    propag(2*nod,st,mij);
    propag(2*nod+1,mij+1,dr);

    int rez;
    if(Max[2*nod+1]>val)
        rez=src(2*nod+1,mij+1,dr,val);
    else
        rez=src(2*nod,st,mij,val);

    Max[nod]=max(Max[2*nod],Max[2*nod+1]);
    return rez;
}

int query(int nod, int st, int dr, int poz)
{
    if(st==dr)
        return Max[nod];

    int mij=(st+dr)/2;
    propag(2*nod,st,mij);
    propag(2*nod+1,mij+1,dr);

    int rez;
    if(poz<=mij)
        rez=query(2*nod,st,mij,poz);
    else
        rez=query(2*nod+1,mij+1,dr,poz);

    Max[nod]=max(Max[2*nod],Max[2*nod+1]);
    return rez;
}

void update(int nod, int st, int dr, int l, int r, int val)
{
    if(l<=st && dr<=r)
    {
        Lazy[nod]=val;
        propag(nod,st,dr);
        return;
    }

    int mij=(st+dr)/2;
    propag(2*nod,st,mij);
    propag(2*nod+1,mij+1,dr);

    if(l<=mij)
        update(2*nod,st,mij,l,r,val);
    if(mij<r)
        update(2*nod+1,mij+1,dr,l,r,val);

    Max[nod]=max(Max[2*nod],Max[2*nod+1]);
}

void modif(int poz, int val) //pun in top10 pe poz val
{
    int fin=10;
    for(int i=poz; i<=10; i++)
    {
        if(Top10[i]==val)
        {
            fin=i;
            break;
        }
    }

    for(int i=fin-1; i>=poz; i--)
        Top10[i+1]=Top10[i];

    Top10[poz]=val;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,a;
    cin>>n>>a;

    for(int i=1; i<=n; i++)
    {
        cin>>A[i];
        if(A[i]>n-10)
            Top10[n-A[i]+1]=i;
    }

    int st=a-1;
    int dr=a+1;
    A[0]=A[n+1]=1000000000;
    while(1)
    {
        if(st==0 && dr==n+1)
            break;

        if(A[st]<A[dr])
        {
            Coresp[st]=dr;
            st--;
        }
        else
            dr++;
    }

    build(1,1,a-1);

    int nrq;
    cin>>nrq;
    for(int q=1; q<=nrq; q++)
    {
        char tip;
        cin>>tip;

        if(tip=='E')
        {
            int x,poz;
            cin>>x>>poz;

            if(x<a)
            {
                int coresp=query(1,1,a-1,x);
                int scoate=n+1;
                int lst=0; //cel mai din dreapta din st lui x care nu poate fi scos de scoate
                for(int i=poz-1; i>=1; i--)
                {
                    if(Top10[i]>=coresp)
                    {
                        if(scoate>Top10[i])
                        {
                            scoate=Top10[i];
                            lst=0;
                        }
                    }
                    else if(Top10[i]<x)
                        lst=max(lst,Top10[i]);
                }

                update(1,1,a-1,lst+1,x,scoate);
            }
            else if(x>a)
            {
                int coresp=src(1,1,a-1,x);
                int scoate=0;
                for(int i=poz-1; i>=1; i--)
                {
                    if(Top10[i]<=coresp)
                        scoate=max(scoate,Top10[i]);
                }

                if(scoate+1<=coresp)
                    update(1,1,a-1,scoate+1,coresp,x);
            }

            modif(poz,x);
        }
        else
        {
            int x;
            cin>>x;
            if(x==a)
            {
                cout<<"0\n";
            }
            else if(x<a)
            {
                int coresp=query(1,1,a-1,x);
                cout<<coresp-x-1<<"\n";
            }
            else
            {
                int coresp=src(1,1,a-1,x);
                cout<<x-coresp-1<<"\n";
            }
        }
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50