Submission #678214

#	Time	Username	Problem	Language	Result	Execution time	Memory
678214		haxorman	Cake (CEOI14_cake)	C++14	30 / 100	2091 ms	5676 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;

    vector<pair<int,int>> nums;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        nums.push_back({arr[i], i});
        update(i, arr[i]);
    }
    sort(nums.begin(), nums.end(), greater<pair<int,int>>());

    while (nums.size() > 10) {
        nums.pop_back();
    }

    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 ind, e;
            cin >> ind >> e;
            
            auto it = find(nums.begin(), nums.end(), make_pair(arr[ind], ind));
            if (it != nums.end()) {
                nums.erase(it);
            }

            for (int i = 0; i < nums.size(); ++i) {
                if (i == e - 1) {
                    int val = nums[i].first + 1;
                    update(ind, val);
                    arr[ind] = val;

                    nums.insert(nums.begin() + i, {val, ind});
                    break;
                }
                else {
                    nums[i].first += 2;
                    update(nums[i].second, nums[i].first);
                    arr[nums[i].second] = nums[i].first;
                }
            }

            while (nums.size() > 10) {
                nums.pop_back();
            }
        }
    }
}

Compilation message (stderr)

cake.cpp: In function 'int32_t main()':
cake.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (int i = 0; i < nums.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~

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