oj.uz

Submission #230122

# Submission time Handle Problem Language Result Execution time Memory
230122 2020-05-08T13:51:31 Z nicolaalexandra Cake (CEOI14_cake) C++14
100 / 100
 1318 ms 25716 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory 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 10 ms 512 KB Output is correct
5 Correct 21 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 5624 KB Output is correct
2 Correct 268 ms 5624 KB Output is correct
3 Correct 353 ms 5504 KB Output is correct
4 Correct 136 ms 5504 KB Output is correct
5 Correct 701 ms 6904 KB Output is correct
6 Correct 549 ms 7288 KB Output is correct
7 Correct 408 ms 6912 KB Output is correct
8 Correct 196 ms 7288 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 9464 KB Output is correct
2 Correct 70 ms 9336 KB Output is correct
3 Correct 56 ms 9208 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 247 ms 20344 KB Output is correct
6 Correct 213 ms 20216 KB Output is correct
7 Correct 92 ms 20088 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1024 KB Output is correct
2 Correct 45 ms 1272 KB Output is correct
3 Correct 105 ms 4984 KB Output is correct
4 Correct 138 ms 4984 KB Output is correct
5 Correct 176 ms 1888 KB Output is correct
6 Correct 192 ms 6896 KB Output is correct
7 Correct 163 ms 3192 KB Output is correct
8 Correct 257 ms 9976 KB Output is correct
9 Correct 1298 ms 25716 KB Output is correct
10 Correct 594 ms 5368 KB Output is correct
11 Correct 792 ms 7716 KB Output is correct
12 Correct 1318 ms 22520 KB Output is correct
13 Correct 863 ms 25392 KB Output is correct