Submission #676578

#	Time	Username	Problem	Language	Result	Execution time	Memory
676578		vjudge1	Cake (CEOI14_cake)	C++17	0 / 100	2099 ms	24608 KiB

cake

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

#define double long double

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

double seg[2 * SZ];

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

double 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, double 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;
}

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

        update(i, x);
        nums.insert(-x);
    }

    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;
            
            nums.erase(-query(i, i));
            if (e == 1) {
                update(i, -(*nums.begin() - 1));
                nums.insert(*nums.begin() - 1);
            }
            else {
                int ind = 2;
                auto it = nums.begin();
                while (ind < e) {
                    ++it, ++ind;
                }
                
                int val = ((*it++) + (*it)) / 2;
                update(i, -val);
                nums.insert(val);
            }
        }
    }
}

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