oj.uz

Submission #391838

# Submission time Handle Problem Language Result Execution time Memory
391838 2021-04-20T03:31:15 Z wiwiho Cake (CEOI14_cake) C++14
30 / 100
 2000 ms 14152 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 q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'F'){
            int b;
            cin >> b;

            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";
                }
            }
            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;
        }
    }

    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 204 KB Output is correct
4 Correct 7 ms 372 KB Output is correct
5 Correct 79 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 720 KB Output is correct
2 Correct 234 ms 844 KB Output is correct
3 Correct 280 ms 844 KB Output is correct
4 Correct 200 ms 844 KB Output is correct
5 Correct 409 ms 1640 KB Output is correct
6 Correct 361 ms 1672 KB Output is correct
7 Correct 296 ms 1672 KB Output is correct
8 Correct 230 ms 1688 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 5960 KB Time limit exceeded
2 Execution timed out 2062 ms 5936 KB Time limit exceeded
3 Execution timed out 2045 ms 5916 KB Time limit exceeded
4 Correct 1 ms 204 KB Output is correct
5 Execution timed out 2074 ms 14044 KB Time limit exceeded
6 Execution timed out 2071 ms 14052 KB Time limit exceeded
7 Execution timed out 2084 ms 14040 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 500 KB Output is correct
2 Correct 194 ms 804 KB Output is correct
3 Execution timed out 2085 ms 3212 KB Time limit exceeded
4 Execution timed out 2079 ms 3236 KB Time limit exceeded
5 Correct 297 ms 708 KB Output is correct
6 Execution timed out 2077 ms 4100 KB Time limit exceeded
7 Correct 1345 ms 1348 KB Output is correct
8 Correct 482 ms 5788 KB Output is correct
9 Execution timed out 2078 ms 14044 KB Time limit exceeded
10 Correct 993 ms 1524 KB Output is correct
11 Execution timed out 2093 ms 1908 KB Time limit exceeded
12 Execution timed out 2082 ms 11400 KB Time limit exceeded
13 Execution timed out 2078 ms 14152 KB Time limit exceeded