oj.uz

답안 #233919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233919 2020-05-22T11:40:47 Z Andrei_Cotor 케이크 (CEOI14_cake) C++11
100 / 100
 374 ms 7444 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 10 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 2284 KB Output is correct
2 Correct 177 ms 2168 KB Output is correct
3 Correct 265 ms 2296 KB Output is correct
4 Correct 156 ms 2296 KB Output is correct
5 Correct 298 ms 2424 KB Output is correct
6 Correct 230 ms 2552 KB Output is correct
7 Correct 289 ms 2680 KB Output is correct
8 Correct 189 ms 2552 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 3960 KB Output is correct
2 Correct 59 ms 3832 KB Output is correct
3 Correct 54 ms 3704 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 82 ms 6200 KB Output is correct
6 Correct 77 ms 6264 KB Output is correct
7 Correct 73 ms 6008 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 896 KB Output is correct
2 Correct 30 ms 1024 KB Output is correct
3 Correct 54 ms 2304 KB Output is correct
4 Correct 55 ms 2296 KB Output is correct
5 Correct 68 ms 1784 KB Output is correct
6 Correct 94 ms 3320 KB Output is correct
7 Correct 92 ms 2680 KB Output is correct
8 Correct 132 ms 3576 KB Output is correct
9 Correct 358 ms 7444 KB Output is correct
10 Correct 218 ms 3192 KB Output is correct
11 Correct 242 ms 3852 KB Output is correct
12 Correct 374 ms 6904 KB Output is correct
13 Correct 286 ms 7160 KB Output is correct