oj.uz

답안 #229970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229970 2020-05-07T12:12:14 Z Ruxandra985 케이크 (CEOI14_cake) C++14
100 / 100
 636 ms 8340 KB 
#include <bits/stdc++.h>
#define DIMN 250010
using namespace std;

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

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 , int 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]);

}

int query_fixed (int nod , int st , int dr , int l , int r){
    int mid = (st + dr)/2;
    int 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 , int 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[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 , idx , poz , j , x , elem = 0 , ok , val;
    char c;

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

    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        aux[i] = v[i];

        if (v[i] > n - 10)
            w[++elem] = make_pair(v[i] , i);
    }

    sort (w + 1 , w + elem + 1);

    w[elem + 1] = make_pair(n + 1 , 0);

    build (1 , 1 , n);

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

        c = fgetc(fin);

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

            ok = 0;
            for (i = 1 ; i <= elem ; i++){
                if (w[i].second == idx){
                    ok = i;
                    break;
                }
            }

            j = elem - poz + 1; /// aia pe care trebuie sa ajunga idx

            if (ok == j)
                continue;

            if (ok == 0)
                ok = 1;

            val = w[j + 1].first;

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

            for (i = j + 1 ; i <= elem ; i++){
                w[i].first++;
                aux[w[i].second] = w[i].first;
                update (1 , 1 , n , w[i].second , w[i].first);
            }
            w[elem + 1].first++;

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

            w[j] = make_pair(val , idx);

            /// val e noua valoare

            aux[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:131: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:134:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~
cake.cpp:147: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:153: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:195: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
15.0 / 15.0

# 결과 실행 시간 메모리 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 8 ms 384 KB Output is correct
5 Correct 15 ms 896 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 888 KB Output is correct
2 Correct 195 ms 768 KB Output is correct
3 Correct 227 ms 832 KB Output is correct
4 Correct 153 ms 1016 KB Output is correct
5 Correct 340 ms 1400 KB Output is correct
6 Correct 288 ms 1260 KB Output is correct
7 Correct 246 ms 1240 KB Output is correct
8 Correct 166 ms 1152 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 3960 KB Output is correct
2 Correct 89 ms 3832 KB Output is correct
3 Correct 86 ms 3832 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 130 ms 7288 KB Output is correct
6 Correct 130 ms 7288 KB Output is correct
7 Correct 101 ms 7032 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 632 KB Output is correct
2 Correct 40 ms 760 KB Output is correct
3 Correct 74 ms 2168 KB Output is correct
4 Correct 98 ms 2168 KB Output is correct
5 Correct 120 ms 1004 KB Output is correct
6 Correct 131 ms 2552 KB Output is correct
7 Correct 133 ms 1400 KB Output is correct
8 Correct 137 ms 3452 KB Output is correct
9 Correct 636 ms 8340 KB Output is correct
10 Correct 372 ms 1656 KB Output is correct
11 Correct 466 ms 2680 KB Output is correct
12 Correct 615 ms 7848 KB Output is correct
13 Correct 531 ms 8312 KB Output is correct