oj.uz

답안 #229957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229957 2020-05-07T10:30:05 Z Ruxandra985 케이크 (CEOI14_cake) C++14
0 / 100
 648 ms 34216 KB 
#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;
}

Compilation message

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

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 1920 KB Output isn't correct
2 Incorrect 217 ms 2168 KB Output isn't correct
3 Incorrect 223 ms 2048 KB Output isn't correct
4 Incorrect 214 ms 2068 KB Output isn't correct
5 Incorrect 255 ms 3992 KB Output isn't correct
6 Incorrect 246 ms 3968 KB Output isn't correct
7 Incorrect 250 ms 4064 KB Output isn't correct
8 Incorrect 235 ms 3968 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 15480 KB Output is correct
2 Correct 151 ms 15328 KB Output is correct
3 Correct 145 ms 15196 KB Output is correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Correct 266 ms 33016 KB Output is correct
6 Incorrect 259 ms 33016 KB Output isn't correct
7 Correct 231 ms 32888 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 896 KB Output isn't correct
2 Incorrect 39 ms 1408 KB Output isn't correct
3 Incorrect 95 ms 7928 KB Output isn't correct
4 Incorrect 93 ms 7792 KB Output isn't correct
5 Incorrect 91 ms 1016 KB Output isn't correct
6 Incorrect 177 ms 9080 KB Output isn't correct
7 Incorrect 139 ms 2680 KB Output isn't correct
8 Incorrect 184 ms 14968 KB Output isn't correct
9 Incorrect 648 ms 34216 KB Output isn't correct
10 Incorrect 271 ms 1912 KB Output isn't correct
11 Incorrect 374 ms 5112 KB Output isn't correct
12 Incorrect 604 ms 31096 KB Output isn't correct
13 Incorrect 554 ms 34168 KB Output isn't correct