oj.uz

Submission #362817

# Submission time Handle Problem Language Result Execution time Memory
362817 2021-02-04T12:47:14 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1271 ms 6120 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);
            while(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-2  << 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 381 ms 748 KB Output isn't correct
2 Incorrect 250 ms 752 KB Output isn't correct
3 Incorrect 271 ms 748 KB Output isn't correct
4 Incorrect 175 ms 620 KB Output isn't correct
5 Incorrect 457 ms 1004 KB Output isn't correct
6 Incorrect 386 ms 1004 KB Output isn't correct
7 Incorrect 321 ms 1004 KB Output isn't correct
8 Incorrect 184 ms 876 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 3052 KB Output isn't correct
2 Incorrect 320 ms 2796 KB Output isn't correct
3 Incorrect 311 ms 2796 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 91 ms 3176 KB Output isn't correct
6 Incorrect 320 ms 4712 KB Output isn't correct
7 Incorrect 311 ms 3816 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 492 KB Output isn't correct
2 Incorrect 85 ms 620 KB Output isn't correct
3 Incorrect 157 ms 1648 KB Output isn't correct
4 Incorrect 190 ms 1648 KB Output isn't correct
5 Incorrect 273 ms 748 KB Output isn't correct
6 Incorrect 313 ms 2028 KB Output isn't correct
7 Incorrect 339 ms 1132 KB Output isn't correct
8 Incorrect 184 ms 2284 KB Output isn't correct
9 Incorrect 310 ms 3776 KB Output isn't correct
10 Incorrect 906 ms 1644 KB Output isn't correct
11 Incorrect 1037 ms 2368 KB Output isn't correct
12 Incorrect 1271 ms 6120 KB Output isn't correct
13 Incorrect 380 ms 3788 KB Output isn't correct