oj.uz

Submission #553217

# Submission time Handle Problem Language Result Execution time Memory
553217 2022-04-25T06:24:15 Z Aldas25 Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 7356 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++;
        }
    }
}

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 Execution timed out 2084 ms 2628 KB Time limit exceeded
2 Execution timed out 2025 ms 2764 KB Time limit exceeded
3 Execution timed out 2079 ms 2636 KB Time limit exceeded
4 Execution timed out 2073 ms 2772 KB Time limit exceeded
5 Execution timed out 2078 ms 1856 KB Time limit exceeded
6 Execution timed out 2070 ms 1872 KB Time limit exceeded
7 Execution timed out 2079 ms 1872 KB Time limit exceeded
8 Execution timed out 2073 ms 1996 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 3980 KB Output isn't correct
2 Incorrect 45 ms 3784 KB Output isn't correct
3 Incorrect 42 ms 3692 KB Output isn't correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 96 ms 7352 KB Output isn't correct
6 Incorrect 96 ms 7356 KB Output isn't correct
7 Incorrect 84 ms 7216 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 920 KB Output isn't correct
2 Incorrect 140 ms 988 KB Output isn't correct
3 Incorrect 1961 ms 2392 KB Output isn't correct
4 Incorrect 1945 ms 2688 KB Output isn't correct
5 Incorrect 195 ms 1696 KB Output isn't correct
6 Execution timed out 2087 ms 2884 KB Time limit exceeded
7 Incorrect 1070 ms 2572 KB Output isn't correct
8 Execution timed out 2089 ms 2908 KB Time limit exceeded
9 Execution timed out 2064 ms 6508 KB Time limit exceeded
10 Incorrect 663 ms 5080 KB Output isn't correct
11 Execution timed out 2094 ms 3148 KB Time limit exceeded
12 Execution timed out 2081 ms 5292 KB Time limit exceeded
13 Execution timed out 2088 ms 6328 KB Time limit exceeded