Submission #553242

#	Time	Username	Problem	Language	Result	Execution time	Memory
553242		Aldas25	Cake (CEOI14_cake)	C++14	0 / 100	2078 ms	1048576 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++;
        }
    }
}

void changeCake (int id, int e) {

    //cntE++;

    REP(e-1) {
        auto p = q.top();
        q.pop();
        p.f++;
        d[p.s]++;
        tmp.push(p);
    }
    int x = q.top().f;
    d[id] = x+1;
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        if (p.s != id) tmp.push(p);
    }
    q.push({d[id], id});

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

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;

            changeCake (id, e);


            /*cout << " d: ";
            FOR(j, 1, n) cout << d[j] << " ";
            cout << endl;I*/

            //precalc();

            //cout << " prec: ";
            //FOR(j, 1, n) cout << prec[j] << " ";
            //cout << endl;
        } 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