oj.uz

Submission #676568

# Submission time Handle Problem Language Result Execution time Memory
676568 2022-12-31T09:52:54 Z vjudge1 Cake (CEOI14_cake) C++17
20 / 100
 2000 ms 5240 KB 
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll mod = 1000000007;

int n, s;
int a[250001], ans[250001];
bool b[250001];
vector<pair<int, int>> v;

void update(int j, int y) {
    if(j != -1) {
        sort(v.rbegin(), v.rend());
        a[j] = v[y - 1].first;
        for(int i = y - 1; i < n; i++) {
            if(v[i].second != j) {
                v[i].first--;
                a[v[i].second] = v[i].first;
            }
            else
                v[i].first = a[j];
        }
    }
    for(int i = 1; i <= n; i++)
        ans[i] = b[i] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({-a[s], s});
    b[s] = 1;
    int x = 0;
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();
        ans[cur] = x++;
        if(cur > 1 && !b[cur - 1]) {
            pq.push({-a[cur - 1], cur - 1});
            b[cur - 1] = 1;
        }
        if(cur < n && !b[cur + 1]) {
            pq.push({-a[cur + 1], cur + 1});
            b[cur + 1] = 1;
        }
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> s;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        v.push_back({a[i], i});
    }
    update(-1, -1);
    int q;
    cin >> q;
    while(q--) {
        char ch;
        cin >> ch;
        if(ch == 'E') {
            int i, x;
            cin >> i >> x;
            update(i, x);
        }
        else {
            int x;
            cin >> x;
            cout << ans[x] << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 94 ms 400 KB Output is correct
5 Execution timed out 2086 ms 768 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 608 KB Time limit exceeded
2 Execution timed out 2074 ms 596 KB Time limit exceeded
3 Execution timed out 2065 ms 708 KB Time limit exceeded
4 Execution timed out 2079 ms 596 KB Time limit exceeded
5 Execution timed out 2080 ms 888 KB Time limit exceeded
6 Execution timed out 2088 ms 1016 KB Time limit exceeded
7 Execution timed out 2072 ms 888 KB Time limit exceeded
8 Execution timed out 2089 ms 856 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 2656 KB Output is correct
2 Correct 412 ms 2608 KB Output is correct
3 Correct 375 ms 2668 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 738 ms 5240 KB Output is correct
6 Correct 887 ms 5224 KB Output is correct
7 Correct 870 ms 5140 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 480 KB Time limit exceeded
2 Execution timed out 2084 ms 744 KB Time limit exceeded
3 Execution timed out 2082 ms 1308 KB Time limit exceeded
4 Execution timed out 2074 ms 1332 KB Time limit exceeded
5 Execution timed out 2089 ms 512 KB Time limit exceeded
6 Execution timed out 2078 ms 1748 KB Time limit exceeded
7 Execution timed out 2088 ms 640 KB Time limit exceeded
8 Execution timed out 2084 ms 2100 KB Time limit exceeded
9 Execution timed out 2097 ms 4600 KB Time limit exceeded
10 Execution timed out 2090 ms 496 KB Time limit exceeded
11 Execution timed out 2078 ms 812 KB Time limit exceeded
12 Execution timed out 2085 ms 3808 KB Time limit exceeded
13 Execution timed out 2097 ms 4556 KB Time limit exceeded