제출 #676543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676543		vjudge1	케이크 (CEOI14_cake)	C++17	0 / 100	2094 ms	7732 KiB

cake

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50