oj.uz

Submission #363419

# Submission time Handle Problem Language Result Execution time Memory
363419 2021-02-05T21:21:44 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1128 ms 11240 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 3e5 + 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 264 ms 876 KB Output isn't correct
2 Incorrect 149 ms 748 KB Output isn't correct
3 Incorrect 201 ms 856 KB Output isn't correct
4 Incorrect 149 ms 876 KB Output isn't correct
5 Incorrect 303 ms 1132 KB Output isn't correct
6 Incorrect 233 ms 1132 KB Output isn't correct
7 Incorrect 237 ms 1152 KB Output isn't correct
8 Incorrect 166 ms 1132 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 3052 KB Output isn't correct
2 Incorrect 316 ms 3180 KB Output isn't correct
3 Incorrect 287 ms 3052 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 366 ms 5608 KB Output isn't correct
6 Incorrect 362 ms 5352 KB Output isn't correct
7 Incorrect 377 ms 5608 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 748 KB Output isn't correct
2 Incorrect 76 ms 896 KB Output isn't correct
3 Incorrect 139 ms 1776 KB Output isn't correct
4 Incorrect 153 ms 1776 KB Output isn't correct
5 Incorrect 256 ms 876 KB Output isn't correct
6 Incorrect 277 ms 2304 KB Output isn't correct
7 Incorrect 306 ms 1272 KB Output isn't correct
8 Incorrect 148 ms 2540 KB Output isn't correct
9 Incorrect 1128 ms 9668 KB Output isn't correct
10 Incorrect 819 ms 1772 KB Output isn't correct
11 Incorrect 917 ms 2700 KB Output isn't correct
12 Incorrect 1089 ms 6120 KB Output isn't correct
13 Incorrect 1006 ms 11240 KB Output isn't correct