제출 #229957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229957		Ruxandra985	케이크 (CEOI14_cake)	C++14	0 / 100	648 ms	34216 KiB

cake

#include <bits/stdc++.h>
#define DIMN 250010
#define ADD 1
using namespace std;

long double v[DIMN] , w[20] , f[20] , aux[DIMN];
pair <long double , int> aint[4 * DIMN] , p[DIMN];

int n;

void build (int nod , int st , int dr){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod] = make_pair( v[st] , st );
        return;
    }

    build (2 * nod , st , mid);
    build (2 * nod + 1 , mid + 1 , dr);

    aint[nod] = max(aint[2 * nod] , aint[2 * nod + 1]);

}


void update (int nod , int st , int dr , int poz , long double val){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod] = make_pair( val , st );
        return;
    }
    if (poz <= mid)
        update (2 * nod , st , mid , poz , val);
    else update (2 * nod + 1 , mid + 1 , dr , poz , val);

    aint[nod] = max(aint[2 * nod] , aint[2 * nod + 1]);

}

long double query_fixed (int nod , int st , int dr , int l , int r){
    int mid = (st + dr)/2;
    long double sol = 0;

    if (l <= st && dr <= r){
        return aint[nod].first;
    }
    if (l <= mid)
        sol = max(sol , query_fixed (2 * nod , st , mid , l , r));
    if (mid + 1 <= r)
        sol = max(sol , query_fixed (2 * nod + 1 , mid + 1 , dr , l , r));

    return sol;
}

int query_check (int nod , int st , int dr , long double val , int l , int r , int type){
    int mid = (st + dr)/2;
    int sol;

    if (type == -1)
        sol = n + 1;
    else sol = 0;

    if (l <= st && dr <= r){

        //printf ("%d %d\n" , st , dr);

        /// vreau fie cel mai mare din interval cu valoarea > val
        /// fie cel mai mic din interval cu aceeasi proprietate


        if (st == dr){
            if (aint[nod].first > val){

                return st; /// pozitie valida

            }
            else {

                /// nu e pozitie valida :(
                if (type == -1)
                    return n + 1;
                else return 0;

            }
        }


        if (type == -1){ /// il vreau pe cel mai mic

            if (aint[2 * nod].first > val)
                return query_check(2 * nod , st , mid , val , l , r , type);
            else if (aint[2 * nod + 1].first > val)
                return query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type);
            else return n + 1; /// nu exista


        }
        else { /// il vreau pe cel mai mare

            if (aint[2 * nod + 1].first > val)
                return query_check(2 * nod + 1 , mid + 1 , dr , val , l , r , type);
            else if (aint[2 * nod].first > val)
                return query_check (2 * nod , st , mid , val , l , r , type);
            else return 0; /// nu exista

        }


    }
    if (l <= mid){
        if (type == -1)
            sol = min(sol , query_check (2 * nod , st , mid , val , l , r , type));
        else sol = max(sol , query_check (2 * nod , st , mid , val , l , r , type));
    }
    if (mid + 1 <= r){
        if (type == -1)
            sol = min(sol , query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type));
        else sol = max(sol , query_check (2 * nod + 1 , mid + 1 , dr , val , l , r , type));
    }
    return sol;
}



int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int a , q , i , sol , elem , idx , poz , j , x;
    long double val , mld;
    char c;

    fscanf (fin,"%d%d",&n,&a);

    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&x);
        v[i] = x * 1.0;
        p[i] = make_pair(v[i] , i);
    }

    sort (p + 1 , p + n + 1);

    for (i = max(1 , n - 9) ; i <= n ; i++){
        if (n >= 10)
            p[i].first = 1000000000LL * (10 - (n - i));
        else p[i].first = 1000000000LL * i;
        v[p[i].second] = p[i].first;
    }

    for (i = 1 ; i <= n ; i++)
        aux[i] = v[i];

    build (1 , 1 , n);

    sort (v + 1 , v + n + 1);

    elem = 0;
    for (i = max(1 , n - 9) ; i <= n ; i++)
        w[++elem] = v[i];

    w[elem + 1] = 11000000000;

    //w[elem + 1] = (n + 1);

    fscanf (fin,"%d\n",&q);

    for (;q;q--){

        c = fgetc(fin);

        if (c == 'E'){
            fscanf (fin,"%d%d\n",&idx,&poz);

            j = elem - poz + 1; /// aia care trb inlocuita

            val = (w[j] + w[j + 1]) / 2;

            for (i = 1 ; i < j ; i++)
                w[i] = w[i + 1];

            w[j] = val;

            /// val e noua valoare

            aux[idx] = val;

            update ( 1 , 1 , n , idx , val );


        }
        else { /// query urile
            fscanf (fin,"%d\n",&x);
            if (a < x){
                val = query_fixed (1 , 1 , n , a + 1 , x);

                sol = x - a + 1 + a - query_check (1 , 1 , n , val , 1 , a - 1 , 1) - 1;
            }
            else if (a == x)
                sol = 1;
            else {
                val = query_fixed (1 , 1 , n , x , a - 1);

                sol = a - x + 1 + query_check (1 , 1 , n , val , a + 1 , n , -1) - a - 1;
            }


            fprintf (fout,"%d\n", sol - 1);

        }
    }


    return 0;
}

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

cake.cpp: In function 'int main()':
cake.cpp:132:23: warning: unused variable 'mld' [-Wunused-variable]
     long double val , mld;
                       ^~~
cake.cpp:135:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&a);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:138:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&x);
         ~~~~~~~^~~~~~~~~~~~~
cake.cpp:167:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d\n",&q);
     ~~~~~~~^~~~~~~~~~~~~~~
cake.cpp:174:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d%d\n",&idx,&poz);
             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:194:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d\n",&x);
             ~~~~~~~^~~~~~~~~~~~~~~

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