oj.uz

Submission #363424

# Submission time Handle Problem Language Result Execution time Memory
363424 2021-02-05T21:49:59 Z nickmet2004 Cake (CEOI14_cake) C++11
73.3333 / 100
 1284 ms 5864 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 100;
int n , s , q , a[N] ,p;
int T[1<<20];
vector<int> top10;
void upd(int d , int id , int l = 1 , int r = n, int pos = 1){
    if(id > r || id < l) return;
    if(l == r){
        T[pos] = d; return;
    }
    int mid = (l + r) >> 1;
    upd(d , id,  l , mid , pos * 2); upd(d , id , mid + 1 , r , pos * 2 + 1);
    T[pos] = max(T[pos * 2 ] , T[pos * 2 + 1]);
}
int get(int L , int R , int l = 1, int r= n , int pos = 1){
    if(r < L || R < l) return -1;
    if(L <= l && r <= R)return T[pos];
    int mid = (l + r)>>1;
    return max(get(L ,R , l , mid , pos * 2) , get(L , R , mid + 1,  r , pos * 2 +1));
}
int go1(int L , int R , int x , int l = 1,  int r = n , int pos = 1){
    if(R < l || r < L) return -1;
    if(L <= l && r <= R){
        if(T[pos] <= x) return -1;
        while(l != r){
            int mid = (l + r) >> 1;
            if(T[pos * 2] > x) pos = pos * 2  , r = mid;
            else pos = pos * 2 + 1 , l = mid + 1;
        }
        return l;
    }
    int mid = (l + r) >> 1;
    int Left = go1(L , R , x , l , mid , pos * 2);
    if(Left != -1) return Left;
    return go1(L , R , x , mid + 1 , r ,pos * 2 + 1);
}
int go2(int L , int R , int x, int l = 1 , int r =n , int pos = 1){
    if(R < l || r < L) return -1;
    if(L <= l && r <= R){
        if(T[pos] <= x) return -1;
        while(l != r){
            int mid = (l + r) >> 1;
            if(T[pos * 2 + 1] > x) pos = pos * 2 + 1 , l = mid + 1;
            else pos = pos * 2 , r = mid;
        }
        return l;
    }
    int mid = (l + r) >> 1;
    int Right = go2(L , R , x , mid + 1 , r , pos * 2 + 1);
    if(Right != -1) return Right;
    return go2(L , R , x , l , mid , pos * 2);
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    for(int i = 1; i <= n; ++i) cin >> a[i] , top10.emplace_back(i);
    for(int i = 1; i <= n; ++i) upd(a[i] , i);
    sort(top10.begin() , top10.end(),  [&](int i , int j){
        return a[i] > a[j];
    });
    while(top10.size() > 10) top10.pop_back();
    //for(int x : top10) cout << x << " ";
    cin >> q;
    p = n;
    while(q--){
        char c;
        cin >> c;
        if(c == 'E'){
            int id, rnk;
            cin >> id >> rnk;
            for(int j =0; j < top10.size(); ++j){
                if(top10[j] == id) {top10.erase(top10.begin() + j); break;}
            }
            rnk--;
            top10.insert(top10.begin() + rnk, id);
            while(top10.size() > 10) top10.pop_back();
            for(int j = rnk; ~j; --j) upd(++p , top10[j]);
            //for(int j  = 0; j < top10.size(); ++j) cout << top10[j] << " ";cout <<endl;
        } else {
            int F;
            cin >> F;
            if(F ==s){cout << 0 << endl; continue;}
            if(F < s){
                int mx = get(F , s - 1);
                //cout << "hii" << endl;
                int y = go1(s + 1 , n  , mx);
                if(y == -1) cout << n - F  << endl;
                else cout << y - F - 1<< endl;
            } else {
                int mx = get(s + 1 , F);
                int y = go2(1 , s-1, mx);
                if(y == -1) cout << F-1  << endl;
                else cout << F - y - 1 << endl;
                //cout << F << " F " << y << " y " << endl;
            }
        }
    }
return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:73:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for(int j =0; j < top10.size(); ++j){
      |                           ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 23 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 684 KB Output is correct
2 Correct 249 ms 620 KB Output is correct
3 Correct 292 ms 620 KB Output is correct
4 Correct 172 ms 620 KB Output is correct
5 Correct 447 ms 1004 KB Output is correct
6 Correct 395 ms 876 KB Output is correct
7 Correct 321 ms 1004 KB Output is correct
8 Correct 186 ms 876 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 3064 KB Output is correct
2 Correct 313 ms 2796 KB Output is correct
3 Correct 322 ms 2796 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Incorrect 457 ms 4260 KB Output isn't correct
6 Incorrect 602 ms 3912 KB Output isn't correct
7 Incorrect 342 ms 3788 KB Output isn't correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 492 KB Output is correct
2 Correct 86 ms 620 KB Output is correct
3 Correct 167 ms 1776 KB Output is correct
4 Correct 192 ms 1800 KB Output is correct
5 Correct 297 ms 748 KB Output is correct
6 Correct 310 ms 2028 KB Output is correct
7 Correct 349 ms 1284 KB Output is correct
8 Correct 187 ms 2412 KB Output is correct
9 Incorrect 476 ms 4968 KB Output isn't correct
10 Correct 912 ms 1644 KB Output is correct
11 Correct 1040 ms 2412 KB Output is correct
12 Correct 1284 ms 5864 KB Output is correct
13 Runtime error 23 ms 3944 KB Execution killed with signal 11