Submission #95367

#	Time	Username	Problem	Language	Result	Execution time	Memory
95367		popovicirobert	케이크 (CEOI14_cake)	C++14	100 / 100	1527 ms	22792 KiB

cake

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 250000;

int arr[MAXN + 1];

struct Data {
    int pos;
    bool operator <(const Data &other) const {
        return arr[pos] > arr[other.pos];
    }
};

multiset <Data> mst;

struct SegTree {
    vector < pair <int, int> > aint;
    int n;
    SegTree(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
        for(int i = 1; i <= 4 * n; i++) {
            aint[i] = {0, i};
        }
    }
    inline void refresh(int nod) {
        if(aint[2 * nod].first > aint[2 * nod + 1].first) {
            aint[nod] = aint[2 * nod];
        }
        else {
            aint[nod] = aint[2 * nod + 1];
        }
    }
    void build(int nod, int left, int right) {
        if(left == right) {
            aint[nod] = {arr[left], left};
        }
        else {
            int mid = (left + right) / 2;
            build(2 * nod, left, mid);
            build(2 * nod + 1, mid + 1, right);
            refresh(nod);
        }
    }
    void update(int nod, int left, int right, int pos, int val) {
        if(left == right) {
            aint[nod] = {val, left};
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }
    pair <int, int> query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            pair <int, int> a, b;
            a = b = {0, 0};
            if(l <= mid) a = query(2 * nod, left, mid, l, r);
            if(mid < r) b = query(2 * nod + 1, mid + 1, right, l, r);
            if(a.first < b.first) {
                return b;
            }
            return a;
        }
    }
    int get_left(int nod, int left, int right, int pos, int val) {
        if(left > pos) {
            return 0;
        }
        if(right <= pos) {
            if(aint[nod].first > val) {
                if(left == right) {
                    return aint[nod].second;
                }
                int mid = (left + right) / 2;
                if(aint[2 * nod + 1].first > val) {
                    return get_left(2 * nod + 1, mid + 1, right, pos, val);
                }
                return get_left(2 * nod, left, mid, pos,  val);
            }
            return 0;
        }
        else {
            int mid = (left + right) / 2;
            int a = get_left(2 * nod, left, mid, pos, val), b = get_left(2 * nod + 1, mid + 1, right, pos, val);
            return max(a, b);
        }
    }
    int get_right(int nod, int left, int right, int pos, int val) {
        if(right < pos) {
            return n + 1;
        }
        if(left >= pos) {
            if(aint[nod].first > val) {
                if(left == right) {
                    return aint[nod].second;
                }
                int mid = (left + right) / 2;
                if(aint[2 * nod].first > val) {
                    return get_right(2 * nod, left, mid, pos, val);
                }
                return get_right(2 * nod + 1, mid + 1, right, pos,  val);
            }
            return n + 1;
        }
        else {
            int mid = (left + right) / 2;
            int a = get_right(2 * nod, left, mid, pos, val), b = get_right(2 * nod + 1, mid + 1, right, pos, val);
            return min(a, b);
        }
    }
};


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q, a;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        mst.insert({i});
    }
    SegTree st(n);
    st.build(1, 1, n);
    cin >> q;
    while(q > 0) {
        q--;
        int pos, e;
        char ch;
        cin >> ch;
        if(ch == 'F') {
            cin >> pos;
            int ans = 0;
            if(a < pos) {
                ans = pos - st.get_left(1, 1, n, a - 1, st.query(1, 1, n, a + 1, pos).first) - 1;
            }
            else if(a > pos) {
                ans = st.get_right(1, 1, n, a + 1, st.query(1, 1, n, pos, a - 1).first) - pos - 1;
            }
            else if(a == pos) {
                ans = 0;
            }
            cout << ans << "\n";
        }
        else {
            cin >> pos >> e;
            auto it = mst.begin();
            int last = arr[it -> pos] + 1;
            int cnt = 0;
            while(cnt < e - 1 && it != mst.end()) {
                int cur = it -> pos;
                cnt += (cur != pos);
                it++;
                last = arr[cur];
                mst.erase(mst.find({cur}));
                arr[cur]++;
                mst.insert({cur});
            }
            mst.erase(mst.find({pos}));
            arr[pos] = last;
            mst.insert({pos});
            it = mst.begin();
            for(i = 0; i < e; i++) {
                st.update(1, 1, n, it -> pos, arr[it -> pos]);
                it++;
            }
            /*for(i = 1; i <= n; i++) {
                cerr << st.query(1, 1, n, i, i).first << " ";
            }
            cerr << "\n";*/
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50