답안 #230115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230115 2020-05-08T12:46:06 Z nicolaalexandra 케이크 (CEOI14_cake) C++14
0 / 100
1977 ms 36984 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1163 ms 28952 KB Output isn't correct
2 Incorrect 858 ms 29080 KB Output isn't correct
3 Incorrect 1002 ms 29176 KB Output isn't correct
4 Incorrect 812 ms 29176 KB Output isn't correct
5 Incorrect 1207 ms 30456 KB Output isn't correct
6 Incorrect 1086 ms 30712 KB Output isn't correct
7 Incorrect 1016 ms 30480 KB Output isn't correct
8 Incorrect 840 ms 30584 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 395 ms 9464 KB Output isn't correct
2 Incorrect 348 ms 9336 KB Output isn't correct
3 Incorrect 333 ms 9420 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Incorrect 606 ms 20216 KB Output isn't correct
6 Incorrect 585 ms 20268 KB Output isn't correct
7 Incorrect 445 ms 20228 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 155 ms 2168 KB Output isn't correct
2 Incorrect 123 ms 2424 KB Output isn't correct
3 Incorrect 244 ms 6836 KB Output isn't correct
4 Incorrect 277 ms 6904 KB Output isn't correct
5 Incorrect 437 ms 5368 KB Output isn't correct
6 Incorrect 440 ms 10360 KB Output isn't correct
7 Incorrect 514 ms 7928 KB Output isn't correct
8 Incorrect 534 ms 19320 KB Output isn't correct
9 Incorrect 1977 ms 36728 KB Output isn't correct
10 Incorrect 1463 ms 17016 KB Output isn't correct
11 Incorrect 1659 ms 19320 KB Output isn't correct
12 Incorrect 1959 ms 34024 KB Output isn't correct
13 Incorrect 1838 ms 36984 KB Output isn't correct