oj.uz

Submission #363421

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

using namespace std;
const int N = 3e5 + 100;
int n , s , q , a[N] ,p;
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();
    p = n;
    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);
            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 -1 << endl;
                else cout << F - s + y -1<< endl;
            }
        }
    }

return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int j = 0; j < top10.size(); ++j){
      |                            ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 23 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 1152 KB Output is correct
2 Correct 156 ms 1004 KB Output is correct
3 Correct 211 ms 1132 KB Output is correct
4 Correct 153 ms 1132 KB Output is correct
5 Correct 298 ms 1644 KB Output is correct
6 Correct 245 ms 1648 KB Output is correct
7 Correct 229 ms 1388 KB Output is correct
8 Correct 161 ms 1516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 3436 KB Output is correct
2 Correct 305 ms 3308 KB Output is correct
3 Correct 292 ms 3264 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 375 ms 5992 KB Output is correct
6 Correct 359 ms 5680 KB Output is correct
7 Correct 342 ms 5736 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1004 KB Output is correct
2 Correct 79 ms 1084 KB Output is correct
3 Correct 142 ms 2288 KB Output is correct
4 Correct 154 ms 2288 KB Output is correct
5 Correct 246 ms 1260 KB Output is correct
6 Correct 273 ms 2540 KB Output is correct
7 Correct 313 ms 1772 KB Output is correct
8 Correct 141 ms 2796 KB Output is correct
9 Correct 1103 ms 7204 KB Output is correct
10 Correct 839 ms 1912 KB Output is correct
11 Correct 920 ms 2872 KB Output is correct
12 Correct 1091 ms 6184 KB Output is correct
13 Correct 1025 ms 7224 KB Output is correct