oj.uz

Submission #553218

# Submission time Handle Problem Language Result Execution time Memory
553218 2022-04-25T06:29:40 Z Aldas25 Cake (CEOI14_cake) C++14
10 / 100
 2000 ms 4964 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) {
    int del = n-e+1;
    FOR(i, 1, n) if (d[id] <= d[i] && d[i]<=del) d[i]--;
    d[id] = del;

    return;

    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();}
}

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;*/

            precalc();
        } 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 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 596 KB Time limit exceeded
2 Execution timed out 2071 ms 596 KB Time limit exceeded
3 Execution timed out 2079 ms 596 KB Time limit exceeded
4 Execution timed out 2071 ms 596 KB Time limit exceeded
5 Execution timed out 2076 ms 856 KB Time limit exceeded
6 Execution timed out 2085 ms 856 KB Time limit exceeded
7 Execution timed out 2084 ms 856 KB Time limit exceeded
8 Execution timed out 2074 ms 856 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2568 KB Output is correct
2 Correct 50 ms 2420 KB Output is correct
3 Correct 50 ms 2416 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 156 ms 4964 KB Output is correct
6 Correct 165 ms 4940 KB Output is correct
7 Correct 104 ms 4792 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 428 KB Output isn't correct
2 Correct 548 ms 580 KB Output is correct
3 Execution timed out 2083 ms 1412 KB Time limit exceeded
4 Execution timed out 2072 ms 1448 KB Time limit exceeded
5 Incorrect 661 ms 696 KB Output isn't correct
6 Execution timed out 2075 ms 1748 KB Time limit exceeded
7 Execution timed out 2084 ms 1016 KB Time limit exceeded
8 Execution timed out 2086 ms 2000 KB Time limit exceeded
9 Execution timed out 2086 ms 4376 KB Time limit exceeded
10 Execution timed out 2070 ms 1356 KB Time limit exceeded
11 Execution timed out 2098 ms 904 KB Time limit exceeded
12 Execution timed out 2089 ms 3720 KB Time limit exceeded
13 Execution timed out 2058 ms 4384 KB Time limit exceeded