제출 #230122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230122		nicolaalexandra	케이크 (CEOI14_cake)	C++14	100 / 100	1318 ms	25716 KiB

cake

#include <bits/stdc++.h>
#define DIM 250010
#define DIMBUFF 10000000
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,pos;
char ch;
char buff[DIMBUFF];

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 get_nr (){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        pos++;
    }
    return nr;
}
char get_char (){

    while (buff[pos] != 'E' && buff[pos] != 'F')
        pos++;
    char ch = buff[pos];
    pos++;
    return ch;

}
int main (){

    //FILE *fin = fopen ("cake.in","r");
    //FILE *fout = fopen ("cake.out","w");

    FILE *fin = stdin;
    FILE *fout = stdout;


    fread (buff,1,DIMBUFF,fin);

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

    build (1,1,n);

    //cin>>q;
    q = get_nr();
    for (;q--;){
        //cin>>ch;
        ch = get_char();
        if (ch == 'E'){
           // cin>>poz>>x;
            poz = get_nr(), x = get_nr();
            /// mai intai verific daca e cumva deja a x - a valoare
            int pas = 0, ok = 0;
            for (set<pair<int,int> > :: reverse_iterator it = s.rbegin();it != s.rend();it++){
                pas++;
                if (pas == x){
                    if (it->second == poz)
                        ok = 1;
                    break;
                }
            }
            if (ok)
                continue;

            /// iau cele mai mari x-1 valori si pe poz o sa pun a x-1 a valoare
            pas = 0;
            int val = get_val (1,1,n,poz), aux = 0;
            w.clear();
            while (1){
                set <pair<int,int> > :: reverse_iterator it = s.rbegin();
                pas++;

                if (pas == x){
                    aux = it->first;

                    update (1,1,n,poz,aux+1);
                    w.push_back(make_pair(aux+1,poz));
                    s.erase(make_pair(val,poz));

                    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));


           // for (i=1;i<=n;i++)
            //    cout<<get_val(1,1,n,i)<<" ";
           // cout<<"\n";
            continue;
        }

        //cin>>poz;
        poz = get_nr();
        if (poz == a){
            fprintf(fout,"0\n");
            //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,sol);

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

            //cout<<sol_poz - poz - 1<<"\n";
            fprintf(fout,"%d\n",sol_poz - poz - 1);

        } else {

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

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

            //cout<<poz - sol_poz - 1<<"\n";
            fprintf(fout,"%d\n",poz - sol_poz - 1);

        }
    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:147:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,DIMBUFF,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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