Submission #677634

#	Time	Username	Problem	Language	Result	Execution time	Memory
677634		vjudge1	Cake (CEOI14_cake)	C++17	0 / 100	2095 ms	16984 KiB

cake

#include <bits/stdc++.h>
using namespace std;

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));

int seg[2 * SZ];

void update(int pos, int val) {
    seg[pos += SZ - 1] = val;
    
    for (pos /= 2; pos; pos /= 2) {
        seg[pos] = max(seg[2 * pos], seg[2 * pos + 1]);
    }
}

int query(int a, int b, int ind = 1, int l = 1, int r = SZ) {
    if (l > b || r < a) {
        return 0;
    }

    if (a <= l && r <= b) {
        return seg[ind];
    }

    int mid = (l + r) / 2;
    return max(query(a, b, 2 * ind, l, mid),
               query(a, b, 2 * ind + 1, mid + 1, r));
}

int walk(int a, int b, int val, bool dir, int ind = 1, int l = 1, int r = SZ) {
    if (l > b || r < a || seg[ind] < val) {
        return 0;
    }
    
    int mid = (l + r) / 2;
    if (a <= l && r <= b) {
        if (l == r) {
            return l;
        }
        else if ((!dir && seg[2 * ind] > val) || (dir && seg[2 * ind + 1] < val)) {
            walk(a, b, val, dir, 2 * ind, l, mid);
        }
        else {
            walk(a, b, val, dir, 2 * ind + 1, mid + 1, r);
        }
    }
    
    int ret = 0;
    ret = (!dir ? walk(a, b, val, dir, 2 * ind, l, mid) :
                  walk(a, b, val, dir, 2 * ind + 1, mid + 1, r));

    if (!ret) {
        ret = (!dir ? walk(a, b, val, dir, 2 * ind + 1, mid + 1, r) :
                      walk(a, b, val, dir, 2 * ind, l, mid));
    }

    return ret;
}

int arr[mxN];

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
    int n, a;
    cin >> n >> a;
    
    set<pair<int,int>> nums;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];

        nums.insert({-arr[i], i});
        update(i, arr[i]);
    }

    int q;
    cin >> q;
    while (q--) {
        char type;
        cin >> type;

        if (type == 'F') {
            int b;
            cin >> b;
            
            if (b == a) {
                cout << "0\n";
            }
            else if (b < a) {
                int mx = query(b, a - 1);
                int ind = walk(min(n, a + 1), n, mx, false);
                if (!ind) {
                    ind = n + 1;
                }

                cout << (ind - a) + (a - b - 1) << "\n";
            }
            else {
                int mx = query(a + 1, b);
                int ind = walk(1, max(1, a - 1), mx, true);
                
                cout << (a - ind - 1) + (b - a) << "\n";
            }
        }
        else {
            int i, e;
            cin >> i >> e;
            

            auto it = nums.begin();
            int ind = 1;
            vector<pair<int,int>> change;
            while (ind < e) {
                change.push_back(*it);
                ++it, ++ind;
            }
            
            for (auto x : change) {
                int cur = -x.first;
                update(x.second, cur + 1);

                nums.erase(x);
                nums.insert({x.first - 1, x.second});
            }

            int val = (-((*it).first)) + 1;
            nums.erase({-arr[i], i});
            nums.insert({-val, i});
            
            update(i, val);

            while (nums.size() > 10) {
                nums.erase(*nums.rbegin());
            }
        }
    }
}

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