oj.uz

Submission #362813

# Submission time Handle Problem Language Result Execution time Memory
362813 2021-02-04T12:40:49 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1326 ms 11684 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 - 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: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 403 ms 5036 KB Output isn't correct
2 Incorrect 250 ms 5228 KB Output isn't correct
3 Incorrect 284 ms 5228 KB Output isn't correct
4 Incorrect 187 ms 5356 KB Output isn't correct
5 Incorrect 462 ms 5868 KB Output isn't correct
6 Incorrect 390 ms 5992 KB Output isn't correct
7 Incorrect 396 ms 5740 KB Output isn't correct
8 Incorrect 195 ms 5992 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 4256 KB Output isn't correct
2 Incorrect 327 ms 4076 KB Output isn't correct
3 Incorrect 323 ms 4204 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 106 ms 4712 KB Output isn't correct
6 Incorrect 326 ms 6888 KB Output isn't correct
7 Incorrect 324 ms 5992 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 928 KB Output isn't correct
2 Incorrect 107 ms 1004 KB Output isn't correct
3 Incorrect 199 ms 2544 KB Output isn't correct
4 Incorrect 186 ms 2544 KB Output isn't correct
5 Incorrect 269 ms 1900 KB Output isn't correct
6 Incorrect 316 ms 3692 KB Output isn't correct
7 Incorrect 343 ms 2796 KB Output isn't correct
8 Incorrect 185 ms 4844 KB Output isn't correct
9 Incorrect 314 ms 6156 KB Output isn't correct
10 Incorrect 931 ms 5320 KB Output isn't correct
11 Incorrect 1064 ms 6588 KB Output isn't correct
12 Incorrect 1326 ms 11684 KB Output isn't correct
13 Incorrect 396 ms 6760 KB Output isn't correct