Submission #230115

#	Time	Username	Problem	Language	Result	Execution time	Memory
230115		nicolaalexandra	Cake (CEOI14_cake)	C++14	0 / 100	1977 ms	36984 KiB

cake

#include <bits/stdc++.h>
#define DIM 250010
using namespace std;
struct segment_tree{
    int maxi,poz;
} aint[DIM*4];

int v[DIM];
set <pair<int,int> > s;
vector <pair<int,int> > w;
int n,a,q,poz,sol_poz,val,sol,x,i;
char ch;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].maxi = v[st];
        aint[nod].poz = st;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    if (aint[nod<<1].maxi > aint[(nod<<1)|1].maxi)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];

}
void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].maxi = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    if (aint[nod<<1].maxi > aint[(nod<<1)|1].maxi)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];
}

void query_maxi (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol = max (sol,aint[nod].maxi);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query_maxi (nod<<1,st,mid,x,y);
    if (y > mid)
        query_maxi ((nod<<1)|1,mid+1,dr,x,y);
}

int get_val (int nod, int st, int dr, int poz){
    if (st == dr)
        return aint[nod].maxi;
    int mid = (st+dr)>>1;
    if (poz <= mid)
        return get_val (nod<<1,st,mid,poz);
    else return get_val ((nod<<1)|1,mid+1,dr,poz);
}

void query (int nod, int st, int dr, int x, int y, int val){
    if (sol_poz)
        return;
    if (st == dr && aint[nod].maxi > val){
        sol_poz = st;
        return;
    }

    if (x <= st && dr <= y){

        if (aint[nod].maxi > val){ /// inseamna ca trb sa i dau split
            int mid = (st+dr)>>1;
            if (aint[nod<<1].maxi <= val)
                query ((nod<<1)|1,mid+1,dr,x,y,val);
            else query ((nod<<1),st,mid,x,y,val);
        }

        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y,val);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y,val);
}

void query2 (int nod, int st, int dr, int x, int y, int val){
    if (sol_poz)
        return;
    if (st == dr && aint[nod].maxi > val){
        sol_poz = st;
        return;
    }

    if (x <= st && dr <= y){

        if (aint[nod].maxi > val){
            int mid = (st+dr)>>1;
            if (aint[(nod<<1)|1].maxi > val)
                query2 ((nod<<1)|1,mid+1,dr,x,y,val);
            else query2 (nod<<1,st,mid,x,y,val);
        }

        return;
    }

    int mid = (st+dr)>>1;
    if (y > mid)
        query2 ((nod<<1)|1,mid+1,dr,x,y,val);
    if (x <= mid)
        query2 (nod<<1,st,mid,x,y,val);
}

int main (){

   // ifstream cin ("cake.in");
   // ofstream cout ("cake.out");

    cin>>n>>a;
    for (i=1;i<=n;i++){
        cin>>v[i];
        s.insert(make_pair(v[i],i));
    }

    build (1,1,n);

    cin>>q;
    for (;q--;){
        cin>>ch;
        if (ch == 'E'){
            cin>>poz>>x;

            /// iau cele mai mari x-1 valori si pe poz o sa pun a x-1 a valoare

            int pas = 0, val = 0;
            w.clear();
            while (1){
                set <pair<int,int> > :: reverse_iterator it = s.rbegin();
                pas++;

                if (pas == x){
                    val = it->first;
                    update (1,1,n,it->second,it->first+1);
                    w.push_back(make_pair(it->first+1,it->second));

                    update (1,1,n,poz,val);
                    w.push_back(make_pair(val,poz));

                    s.erase(make_pair(it->first,it->second));
                    break;
                }

                update (1,1,n,it->second,it->first+1);
                w.push_back(make_pair(it->first+1,it->second));
                s.erase(make_pair(it->first,it->second));

            }
            for (auto it : w)
                s.insert(make_pair(it.first,it.second));

            continue;
        }

        cin>>poz;
        if (poz == a){
            cout<<"0\n";
            continue;
        }

        val = get_val (1,1,n,poz);
        if (poz < a){ /// e in stanga
            sol = 0;
            query_maxi (1,1,n,poz,a-1);

            sol_poz = 0;
            query (1,1,n,a+1,n,val);

            if (!sol_poz) /// inseamna ca toate sunt mai mici
                sol_poz = n+1;

            cout<<sol_poz - poz - 1<<"\n";

        } else {

            sol = 0;
            query_maxi (1,1,n,a+1,poz);

            sol_poz = 0;
            query2 (1,1,n,1,a-1,val);

            cout<<poz - sol_poz - 1<<"\n";

        }
    }


    return 0;
}

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