제출 #442637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442637		prvocislo	케이크 (CEOI14_cake)	C++17	100 / 100	464 ms	14604 KiB

cake

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

const int maxn = 1 << 18; int k = 10;
class intervalac
{
    vector<int> m;
public:
    intervalac(): m(vector<int>(maxn*2, -1)) {}
    void update(int i, int x)
    {
        m[i += maxn] = x;
        for (i = (i >> 1); i > 0; i >>= 1) m[i] = max(m[i<<1], m[i<<1|1]); 
    }
    int maxi(int l, int r)
    {
        int ans = 0;
        for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1)
        {
            if (l&1) ans = max(ans, m[l++]);
            if (r&1) ans = max(ans, m[--r]);
        }
        return ans;
    }
    int small(int x) // najde prvy kolac ktory je vacsi ako x
    {
        for (int i = 2; ; i <<= 1)
        {
            if (m[i] < x) i++;
            if (i >= maxn) return i - maxn;
        }
    }
};
vector<int> t(maxn);
bool cmp(int i, int j) { return t[i] > t[j]; }
intervalac in[2];
int n, q, a;
int ly(int i) { return i > a; } 
int id(int i) { return ly(i) == 0 ? a - 1 - i : i - a - 1; }
void upd(int i, int x) { if (i ^ a) in[ly(i)].update(id(i), x); }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> a; a--; k = min(k, n);
    vector<int> best; // {chut, index}
    for (int i = 0; i < n; i++) cin >> t[i], best.push_back(i), upd(i, t[i]);
    sort(best.begin(), best.end(), cmp), best.resize(k);
    int num = n+1;
    upd(-1, 1e9), upd(n, 1e9);
    cin >> q;
    while (q--)
    {
        char c; cin >> c;
        if (c == 'E') // update
        {
            int i, e; cin >> i >> e; i--, e--;
            for (int j = 0; j < k; j++) if (best[j] == i) best.erase(best.begin()+j);
            best.insert(best.begin()+e, i); best.resize(k);
            for (int i = k-1; i >= 0; i--) t[best[i]] = num++, upd(best[i], t[best[i]]);
        }
        else // query
        {
            int b; cin >> b; b--;
            if (b == a)
            {
                cout << "0\n";
                continue;
            }
            int l = ly(b), i = id(b);
            int mx = in[l].maxi(0, i), cnt = in[l^1].small(mx);
            cout << cnt + abs(a - b) << "\n";
        }
    }
    return 0;
}

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