oj.uz

Submission #363420

# Submission time Handle Problem Language Result Execution time Memory
363420 2021-02-05T21:28:08 Z nickmet2004 Cake (CEOI14_cake) C++11
0 / 100
 1120 ms 6636 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[4*N];
    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--;
            top10.insert(top10.begin() + rnk , id);
            int p = n;
            for(int j = rnk; ~j; --j) u(top10[j] , ++p);
            if(top10.size() > 10) top10.pop_back();
        } 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 285 ms 620 KB Output isn't correct
2 Incorrect 156 ms 620 KB Output isn't correct
3 Incorrect 215 ms 640 KB Output isn't correct
4 Incorrect 156 ms 620 KB Output isn't correct
5 Incorrect 314 ms 1132 KB Output isn't correct
6 Incorrect 243 ms 1132 KB Output isn't correct
7 Incorrect 239 ms 1044 KB Output isn't correct
8 Incorrect 160 ms 1004 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 2924 KB Output isn't correct
2 Incorrect 294 ms 3052 KB Output isn't correct
3 Incorrect 300 ms 2924 KB Output isn't correct
4 Incorrect 1 ms 512 KB Output isn't correct
5 Incorrect 359 ms 5240 KB Output isn't correct
6 Incorrect 374 ms 5352 KB Output isn't correct
7 Incorrect 341 ms 5352 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 620 KB Output isn't correct
2 Incorrect 76 ms 652 KB Output isn't correct
3 Incorrect 135 ms 1648 KB Output isn't correct
4 Incorrect 156 ms 1648 KB Output isn't correct
5 Incorrect 247 ms 1004 KB Output isn't correct
6 Incorrect 271 ms 2028 KB Output isn't correct
7 Incorrect 316 ms 1260 KB Output isn't correct
8 Incorrect 145 ms 2412 KB Output isn't correct
9 Incorrect 1089 ms 6504 KB Output isn't correct
10 Incorrect 854 ms 1644 KB Output isn't correct
11 Incorrect 911 ms 2540 KB Output isn't correct
12 Incorrect 1120 ms 5992 KB Output isn't correct
13 Incorrect 1035 ms 6636 KB Output isn't correct