제출 #490293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490293		SirCovidThe19th	케이크 (CEOI14_cake)	C++17	100 / 100	825 ms	6040 KiB

cake

#include <bits/stdc++.h>
using namespace std;

template<int sz> struct DS{
    int seg[sz * 2];
    void upd(int i, int v){
        seg[i += sz] = v;
        for (i /= 2; i; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]); 
    }
    int qry(int l, int r){ 
        int ans = 0;
        for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) ans = max(ans, seg[l++]);
            if (r % 2 == 0) ans = max(seg[r--], ans);
        }
        return ans;
    }
    int walk(int v){
        int i = 1; 
        while (i < sz) i = (seg[i * 2] < v) ? i * 2 + 1 : i * 2;
        return i - sz - 1;
    }
}; 
const int mN = 2.5e5 + 5, mQ = 5e5 + 5;

int n, a, q; pair<int, int> tmp[mN]; DS<(1 << 19)> L, R;

deque<int> w10; int net = mN;

void ins(int pos, int v){
    if (pos < a) L.upd(a - pos, v);
    if (pos > a) R.upd(pos - a, v);
}
int main(){
    cin >> n >> a; 

    for (int i = 1; i <= n; i++) cin >> tmp[i].first, tmp[i].second = i;
    sort(tmp + 1, tmp + n + 1);

    for (int i = 1; i <= n; i++){
        int pos = tmp[i].second, r = i;
        if (i >= n - 9) r += mQ * 2, w10.push_back(pos);
        ins(pos, r);
    }
    cin >> q; L.upd(a, 1e9); R.upd(n - a + 1, 1e9);
    while (q--){
        int pos; char type; cin >> type >> pos;
        if (type == 'E'){
            int e; cin >> e;
            auto it = find(w10.begin(), w10.end(), pos);
            if (it != w10.end()) w10.erase(it);
            w10.insert(w10.end() - e + 1, pos);
            if (w10.size() > 10) ins(w10[0], ++net), w10.pop_front();
            for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
        }
        else{
            int ans = pos;
            if (pos < a) ans = R.walk(L.qry(1, a - pos)) + a;
            if (pos > a) ans = a - L.walk(R.qry(1, pos - a));
            cout<<abs(pos - ans)<<"\n";
        }
    }
}

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

cake.cpp: In function 'int main()':
cake.cpp:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
      |                             ~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50