oj.uz

Submission #362814

# Submission time Handle Problem Language Result Execution time Memory
362814 2021-02-04T12:43:51 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1326 ms 5992 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 392 ms 748 KB Output isn't correct
2 Incorrect 251 ms 768 KB Output isn't correct
3 Incorrect 278 ms 748 KB Output isn't correct
4 Incorrect 186 ms 760 KB Output isn't correct
5 Incorrect 466 ms 996 KB Output isn't correct
6 Incorrect 384 ms 1004 KB Output isn't correct
7 Incorrect 339 ms 1004 KB Output isn't correct
8 Incorrect 193 ms 1004 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 351 ms 3052 KB Output isn't correct
2 Incorrect 349 ms 2940 KB Output isn't correct
3 Incorrect 321 ms 2924 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 92 ms 3176 KB Output isn't correct
6 Incorrect 337 ms 4716 KB Output isn't correct
7 Incorrect 317 ms 3816 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 492 KB Output isn't correct
2 Incorrect 87 ms 640 KB Output isn't correct
3 Incorrect 157 ms 1648 KB Output isn't correct
4 Incorrect 183 ms 1648 KB Output isn't correct
5 Incorrect 272 ms 1132 KB Output isn't correct
6 Incorrect 309 ms 2060 KB Output isn't correct
7 Incorrect 347 ms 1260 KB Output isn't correct
8 Incorrect 182 ms 2284 KB Output isn't correct
9 Incorrect 313 ms 3560 KB Output isn't correct
10 Incorrect 915 ms 1540 KB Output isn't correct
11 Incorrect 1069 ms 2536 KB Output isn't correct
12 Incorrect 1326 ms 5992 KB Output isn't correct
13 Incorrect 387 ms 3816 KB Output isn't correct