oj.uz

Submission #363418

# Submission time Handle Problem Language Result Execution time Memory
363418 2021-02-05T21:00:24 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1085 ms 12012 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 100;
int n , s , q , a[N];
vector<int> top10;
struct CANCIK_PETRIK_SHOBIL{
    int T[1<<20];
    void upd(int id , int d , int l = 1 , int r = n , int pos = 1){
        if(id < l || id > r) return;
        if(l == r){
            T[pos] = d; return;
        }
        int mid = (l + r) >> 1;
        upd(id , d , l , mid , pos * 2); upd(id ,d ,  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 go(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 *= 2 , r = mid;
                else pos= pos * 2 + 1 , l = mid + 1;
            } return l;
        }
        int mid = (l + r) >> 1;
        int W = go(L , R , x, l , mid , pos * 2);
        if(W != -1) return W;
        return go(L , R , x , mid + 1 , r , pos * 2 + 1);
    }
}L , R;
void u(int id , int d){
    if(id < s) L.upd(s - id , d);
    else R.upd(id - s , d);
}
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);
    sort(top10.begin() , top10.end() , [&](int i , int j){
        return a[i] > a[j];
    });
    for(int i = 1; i <= n; ++i) u(i , a[i]);
    while(top10.size() > 10) top10.pop_back();
    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--;
            if(top10.size() > 10) top10.pop_back();
            top10.insert(top10.begin() + rnk , id);
            int p = n;
            for(int j = rnk; ~j; --j) u(top10[j] , ++p);
        } else {
            int F;
            cin >> F;
            int mx , y;
            if(F == s) {cout << 0 << endl; continue;}
            if(F < s){
                mx = L.get(1 , s - F); y = R.go(1 , n , mx);
                if(y == -1) cout << n - F << endl;
                else cout << s - F + y- 1 << endl;
            } else {
                mx = R.get(1 , F - s); y= L.go(1 , n , mx);
                if(y == -1) cout << F  << endl;
                else cout << F - s + y -1<< endl;
            }
        }
    }

return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             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 263 ms 5100 KB Output isn't correct
2 Incorrect 152 ms 5100 KB Output isn't correct
3 Incorrect 198 ms 5100 KB Output isn't correct
4 Incorrect 150 ms 5248 KB Output isn't correct
5 Incorrect 288 ms 5868 KB Output isn't correct
6 Incorrect 235 ms 5996 KB Output isn't correct
7 Incorrect 224 ms 5868 KB Output isn't correct
8 Incorrect 160 ms 5996 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 4332 KB Output isn't correct
2 Incorrect 297 ms 4204 KB Output isn't correct
3 Incorrect 286 ms 4332 KB Output isn't correct
4 Incorrect 1 ms 492 KB Output isn't correct
5 Incorrect 428 ms 6000 KB Output isn't correct
6 Incorrect 564 ms 6632 KB Output isn't correct
7 Incorrect 310 ms 6120 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 1004 KB Output isn't correct
2 Incorrect 76 ms 1004 KB Output isn't correct
3 Incorrect 149 ms 2672 KB Output isn't correct
4 Incorrect 159 ms 2672 KB Output isn't correct
5 Incorrect 246 ms 1900 KB Output isn't correct
6 Incorrect 267 ms 3728 KB Output isn't correct
7 Incorrect 316 ms 2796 KB Output isn't correct
8 Incorrect 139 ms 4972 KB Output isn't correct
9 Incorrect 449 ms 8680 KB Output isn't correct
10 Incorrect 809 ms 5356 KB Output isn't correct
11 Incorrect 899 ms 6656 KB Output isn't correct
12 Incorrect 1085 ms 12012 KB Output isn't correct
13 Runtime error 24 ms 5608 KB Execution killed with signal 11