oj.uz

Submission #553242

# Submission time Handle Problem Language Result Execution time Memory
553242 2022-04-25T07:36:10 Z Aldas25 Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 1048576 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1375 ms 1048576 KB Execution killed with signal 9
2 Incorrect 214 ms 4812 KB Output isn't correct
3 Incorrect 261 ms 4860 KB Output isn't correct
4 Incorrect 222 ms 4728 KB Output isn't correct
5 Runtime error 1214 ms 1048576 KB Execution killed with signal 9
6 Incorrect 280 ms 5668 KB Output isn't correct
7 Incorrect 227 ms 5472 KB Output isn't correct
8 Incorrect 227 ms 5728 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 2632 KB Time limit exceeded
2 Execution timed out 2059 ms 2576 KB Time limit exceeded
3 Incorrect 914 ms 2596 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 2025 ms 4244 KB Time limit exceeded
6 Execution timed out 2039 ms 4276 KB Time limit exceeded
7 Incorrect 439 ms 4416 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 888 KB Output isn't correct
2 Incorrect 81 ms 844 KB Output isn't correct
3 Incorrect 1008 ms 2296 KB Output isn't correct
4 Incorrect 913 ms 2244 KB Output isn't correct
5 Incorrect 136 ms 1512 KB Output isn't correct
6 Execution timed out 2072 ms 3104 KB Time limit exceeded
7 Incorrect 583 ms 2640 KB Output isn't correct
8 Incorrect 186 ms 4188 KB Output isn't correct
9 Execution timed out 2016 ms 4796 KB Time limit exceeded
10 Incorrect 437 ms 2432 KB Output isn't correct
11 Execution timed out 2078 ms 5232 KB Time limit exceeded
12 Execution timed out 2066 ms 4564 KB Time limit exceeded
13 Execution timed out 2055 ms 692984 KB Time limit exceeded