제출 #553217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553217		Aldas25	Cake (CEOI14_cake)	C++14	0 / 100	2094 ms	7356 KiB

cake

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int MAXN = 500100;

int n, a;
int d[MAXN];
int Q;
priority_queue<pii> q, tmp;
int cntE = 0;

int prec[MAXN];

int query (int b) {
    return prec[b];

    if (a == b)
        return 0;


    int le = a-1, ri = a+1;

    int ans = 1;
    //cout << " b = " << b << endl;
    while (le > 0 || ri <= n) {
            //cout << "   le = " << le << " ri = " << ri << endl;
        if (le == 0 || (ri <= n && d[ri] < d[le])){
            if (ri == b) return ans;
            ri++;
            ans++;
        } else {
            if (le == b) return ans;
            le--;
            ans++;
        }
    }

    return ans;
}

void precalc() {
    prec[a] = 0;

    int le = a-1, ri = a+1;

    int ans = 1;
    //cout << " b = " << b << endl;
    while (le > 0 || ri <= n) {
            //cout << "   le = " << le << " ri = " << ri << endl;
        if (le == 0 || (ri <= n && d[ri] < d[le])){
           // if (ri == b) return ans;
            prec[ri] = ans;
            ri++;
            ans++;
        } else {
            //if (le == b) return ans;
            prec[le] = ans;
            le--;
            ans++;
        }
    }
}

int main()
{
    FAST_IO;

    cin >> n >> a;
    FOR(i, 1, n) cin >> d[i];
    FOR(i, 1, n) q.push({d[i], i});
    while ((int)q.size() > 10) {q.pop();}
precalc();
    cin >> Q;
    while (Q--) {
        char c;
        cin >> c;
        if (c == 'E') {
            int id, e; cin >> id >> e;
            cntE++;

            REP(e-1) {
                auto p = q.top();
                q.pop();
                p.f++;
                d[p.s]++;
                tmp.push(p);
            }
            d[id] = n-e+1 + cntE;
            q.push({d[id], id});

            while (!tmp.empty()) {
                auto p = tmp.top();
                tmp.pop();
                q.push(p);
            }
            while ((int)q.size() > 10) {q.pop();}

            /*cout << " d: ";
            FOR(j, 1, n) cout << d[j] << " ";
            cout << endl;*/
            precalc();
        } else {
            int b; cin >> b;
            cout << query (b)<< "\n";
        }
    }

    return 0;
}

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