oj.uz

답안 #229948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229948 2020-05-07T08:42:20 Z Ruxandra985 케이크 (CEOI14_cake) C++14
0 / 100
 437 ms 18680 KB 
#include <bits/stdc++.h>
#define DIMN 250010
#define ADD 1
using namespace std;

double v[DIMN] , w[20];
pair <double , int> aint[4 * 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 , 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]);

}

double query_fixed (int nod , int st , int dr , int l , int r){
    int mid = (st + dr)/2;
    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 , 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){

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


        if (st == dr){
            if (aint[st].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;
    double val;
    char c;

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

    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%lf",&v[i]);
        //v[i] *= 1000000000.0;
    }

    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] = (n + 1);

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

    for (;q;q--){

        c = fgetc(fin);

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

            /// elem idx va lua valoarea poz in ierarhie

            /// elem ... poz = 1
            /// elem - 1 ... poz = 2

            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

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


        }
        else { /// query urile

            fscanf (fin,"%d\n",&x);
            if (a < x){
                val = query_fixed (1 , 1 , n , a , 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);

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


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

        }
    }


    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:133: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:136:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lf",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:150: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:157: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:181: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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 5344 KB Output isn't correct
2 Incorrect 165 ms 5372 KB Output isn't correct
3 Incorrect 171 ms 5368 KB Output isn't correct
4 Incorrect 156 ms 5496 KB Output isn't correct
5 Incorrect 194 ms 6264 KB Output isn't correct
6 Incorrect 185 ms 6520 KB Output isn't correct
7 Incorrect 191 ms 6520 KB Output isn't correct
8 Incorrect 168 ms 6520 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 7124 KB Output isn't correct
2 Incorrect 95 ms 7160 KB Output isn't correct
3 Incorrect 110 ms 7416 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Incorrect 169 ms 13688 KB Output isn't correct
6 Incorrect 167 ms 13684 KB Output isn't correct
7 Incorrect 138 ms 13816 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 1024 KB Output isn't correct
2 Incorrect 32 ms 1152 KB Output isn't correct
3 Incorrect 66 ms 4008 KB Output isn't correct
4 Incorrect 63 ms 3960 KB Output isn't correct
5 Incorrect 73 ms 1912 KB Output isn't correct
6 Incorrect 121 ms 5244 KB Output isn't correct
7 Incorrect 106 ms 3064 KB Output isn't correct
8 Incorrect 118 ms 7800 KB Output isn't correct
9 Incorrect 437 ms 18680 KB Output isn't correct
10 Incorrect 224 ms 5368 KB Output isn't correct
11 Incorrect 283 ms 7288 KB Output isn't correct
12 Incorrect 413 ms 17824 KB Output isn't correct
13 Incorrect 400 ms 18552 KB Output isn't correct