oj.uz

Submission #676543

# Submission time Handle Problem Language Result Execution time Memory
676543 2022-12-31T08:25:26 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 7732 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].second = 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 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 852 KB Time limit exceeded
2 Execution timed out 2086 ms 852 KB Time limit exceeded
3 Execution timed out 2056 ms 852 KB Time limit exceeded
4 Execution timed out 2088 ms 852 KB Time limit exceeded
5 Execution timed out 2086 ms 1240 KB Time limit exceeded
6 Execution timed out 2092 ms 1240 KB Time limit exceeded
7 Execution timed out 2082 ms 1244 KB Time limit exceeded
8 Execution timed out 2077 ms 1240 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 417 ms 4052 KB Output isn't correct
2 Incorrect 424 ms 3912 KB Output isn't correct
3 Incorrect 395 ms 3832 KB Output isn't correct
4 Correct 1 ms 328 KB Output is correct
5 Incorrect 788 ms 7732 KB Output isn't correct
6 Incorrect 999 ms 7676 KB Output isn't correct
7 Incorrect 926 ms 7444 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 912 KB Time limit exceeded
2 Execution timed out 2052 ms 1004 KB Time limit exceeded
3 Execution timed out 2068 ms 1796 KB Time limit exceeded
4 Execution timed out 2084 ms 1792 KB Time limit exceeded
5 Execution timed out 2076 ms 1104 KB Time limit exceeded
6 Execution timed out 2068 ms 2388 KB Time limit exceeded
7 Execution timed out 2094 ms 1004 KB Time limit exceeded
8 Execution timed out 2054 ms 2816 KB Time limit exceeded
9 Execution timed out 2081 ms 6344 KB Time limit exceeded
10 Execution timed out 2065 ms 1144 KB Time limit exceeded
11 Execution timed out 2078 ms 1172 KB Time limit exceeded
12 Execution timed out 2060 ms 5276 KB Time limit exceeded
13 Execution timed out 2061 ms 6316 KB Time limit exceeded