oj.uz

Submission #391842

# Submission time Handle Problem Language Result Execution time Memory
391842 2021-04-20T03:32:41 Z wiwiho Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 14636 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

using pii = pair<int, int>;

ostream& operator<<(ostream& o, pii p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a;
    cin >> n >> a;

    vector<int> d(n + 1);
    map<int, int, greater<>> rk;
    for(int i = 1; i <= n; i++){
        cin >> d[i];
        rk[d[i]] = i;
    }

    //printv(d, cerr);
    //printv(rk, cerr);

    vector<int> pos(n + 1);
    int l = a, r = a;
    pos[a] = 1;
    for(int i = 2; i <= n; i++){
        if(r == n){
            l--;
            pos[l] = i;
            //cerr << l << " " << i << "\n";
        }
        else if(l == 1){
            r++;
            pos[r] = i;
            //cerr << r << " " << i << "\n";
        }
        else if(d[l - 1] < d[r + 1]){
            l--;
            pos[l] = i;
            //cerr << l << " " << i << "\n";
        }
        else{
            r++;
            pos[r] = i;
            //cerr << r << " " << i << "\n";
        }
    }

    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'F'){
            int b;
            cin >> b;

            cout << pos[b] - 1 << "\n";
            continue;
        }

        int b, e;
        cin >> b >> e;

        vector<int> tmp;
        for(int i = 0; i < e - 1; i++){
            tmp.eb(rk.begin()->S);
            rk.erase(rk.begin());
        }
        tmp.eb(b);
        rk.erase(d[b]);
        while(!tmp.empty()){
            int now = tmp.back();
            tmp.pop_back();
            d[now] = rk.empty() ? 1 : rk.begin()->F + 1;
            rk[d[now]] = now;
        }
        int l = a, r = a;
        pos[a] = 1;
        for(int i = 2; i <= n; i++){
            if(r == n){
                l--;
                pos[l] = i;
                //cerr << l << " " << i << "\n";
            }
            else if(l == 1){
                r++;
                pos[r] = i;
                //cerr << r << " " << i << "\n";
            }
            else if(d[l - 1] < d[r + 1]){
                l--;
                pos[l] = i;
                //cerr << l << " " << i << "\n";
            }
            else{
                r++;
                pos[r] = i;
                //cerr << r << " " << i << "\n";
            }
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 81 ms 860 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 720 KB Time limit exceeded
2 Execution timed out 2083 ms 844 KB Time limit exceeded
3 Execution timed out 2067 ms 844 KB Time limit exceeded
4 Execution timed out 2082 ms 844 KB Time limit exceeded
5 Execution timed out 2097 ms 1612 KB Time limit exceeded
6 Execution timed out 2097 ms 1612 KB Time limit exceeded
7 Execution timed out 2072 ms 1584 KB Time limit exceeded
8 Execution timed out 2081 ms 1672 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6280 KB Output is correct
2 Correct 64 ms 6260 KB Output is correct
3 Correct 63 ms 6132 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 221 ms 14612 KB Output is correct
6 Correct 220 ms 14636 KB Output is correct
7 Correct 129 ms 14532 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 480 KB Output is correct
2 Correct 203 ms 580 KB Output is correct
3 Execution timed out 2082 ms 3316 KB Time limit exceeded
4 Execution timed out 2084 ms 3140 KB Time limit exceeded
5 Correct 313 ms 740 KB Output is correct
6 Execution timed out 2081 ms 4316 KB Time limit exceeded
7 Correct 1465 ms 1380 KB Output is correct
8 Execution timed out 2080 ms 5736 KB Time limit exceeded
9 Execution timed out 2037 ms 14144 KB Time limit exceeded
10 Correct 1014 ms 1524 KB Output is correct
11 Execution timed out 2084 ms 2104 KB Time limit exceeded
12 Execution timed out 2075 ms 11320 KB Time limit exceeded
13 Execution timed out 2081 ms 14044 KB Time limit exceeded