oj.uz

Submission #362816

# Submission time Handle Problem Language Result Execution time Memory
362816 2021-02-04T12:46:26 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1306 ms 5876 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 15;
int n , s , q , a[N];
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;
    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);
            if(top10.size() > 10) top10.pop_back();
            int p = n;
            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  << 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:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int j =0; j < top10.size(); ++j){
      |                           ~~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 398 ms 620 KB Output isn't correct
2 Incorrect 270 ms 748 KB Output isn't correct
3 Incorrect 276 ms 620 KB Output isn't correct
4 Incorrect 174 ms 620 KB Output isn't correct
5 Incorrect 453 ms 876 KB Output isn't correct
6 Incorrect 382 ms 1004 KB Output isn't correct
7 Incorrect 326 ms 1004 KB Output isn't correct
8 Incorrect 185 ms 876 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 2924 KB Output isn't correct
2 Incorrect 319 ms 2796 KB Output isn't correct
3 Incorrect 312 ms 2796 KB Output isn't correct
4 Incorrect 1 ms 492 KB Output isn't correct
5 Incorrect 91 ms 3176 KB Output isn't correct
6 Incorrect 356 ms 4892 KB Output isn't correct
7 Incorrect 315 ms 3816 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 492 KB Output isn't correct
2 Incorrect 91 ms 664 KB Output isn't correct
3 Incorrect 162 ms 1776 KB Output isn't correct
4 Incorrect 179 ms 1772 KB Output isn't correct
5 Incorrect 271 ms 932 KB Output isn't correct
6 Incorrect 308 ms 1944 KB Output isn't correct
7 Incorrect 339 ms 1228 KB Output isn't correct
8 Incorrect 185 ms 2412 KB Output isn't correct
9 Incorrect 311 ms 3560 KB Output isn't correct
10 Incorrect 907 ms 1608 KB Output isn't correct
11 Incorrect 1043 ms 2444 KB Output isn't correct
12 Incorrect 1306 ms 5876 KB Output isn't correct
13 Incorrect 384 ms 3816 KB Output isn't correct