oj.uz

Submission #363422

# Submission time Handle Problem Language Result Execution time Memory
363422 2021-02-05T21:47:16 Z nickmet2004 Cake (CEOI14_cake) C++11
73.3333 / 100
 1271 ms 5992 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 15;
int n , s , q , a[N] ,p;
int T[1<<20] , H[N];
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 10 ms 364 KB Output is correct
5 Correct 28 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 250 ms 620 KB Output is correct
3 Correct 277 ms 692 KB Output is correct
4 Correct 196 ms 620 KB Output is correct
5 Correct 456 ms 1004 KB Output is correct
6 Correct 377 ms 876 KB Output is correct
7 Correct 324 ms 1004 KB Output is correct
8 Correct 183 ms 876 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 2924 KB Output is correct
2 Correct 321 ms 2796 KB Output is correct
3 Correct 307 ms 2668 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 99 ms 3244 KB Output isn't correct
6 Incorrect 313 ms 4712 KB Output isn't correct
7 Incorrect 310 ms 3816 KB Output isn't correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 492 KB Output is correct
2 Correct 92 ms 600 KB Output is correct
3 Correct 164 ms 1648 KB Output is correct
4 Correct 179 ms 1648 KB Output is correct
5 Correct 276 ms 876 KB Output is correct
6 Correct 331 ms 2028 KB Output is correct
7 Correct 342 ms 1132 KB Output is correct
8 Correct 200 ms 2412 KB Output is correct
9 Incorrect 307 ms 3728 KB Output isn't correct
10 Correct 959 ms 1576 KB Output is correct
11 Correct 1093 ms 2412 KB Output is correct
12 Correct 1271 ms 5992 KB Output is correct
13 Incorrect 390 ms 3816 KB Output isn't correct