제출 #363421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363421		nickmet2004	케이크 (CEOI14_cake)	C++11	100 / 100	1103 ms	7224 KiB

cake

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50