Submission #872880

#	Time	Username	Problem	Language	Result	Execution time	Memory
872880		thuanqvbn03	Cake (CEOI14_cake)	C++17	100 / 100	731 ms	12464 KiB

cake

// Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 250005;

struct SegmentTree {
   private:
    int treeSize;
    vector<int> nodes, leaf;
    void initTree(int id, int low, int high, int arr[]) {
        if (low == high) {
            nodes[id] = arr[low];
            leaf[low] = id;
            return;
        }
        int mid = (low + high) / 2;
        initTree(id * 2, low, mid, arr);
        initTree(id * 2 + 1, mid + 1, high, arr);
        nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
    }
    int get(int id, int low, int high, int left, int right) {
        if (low > right || high < left) {
            return 0;
        }
        if (low >= left && high <= right) {
            return nodes[id];
        }
        int mid = (low + high) / 2;
        return max(get(id * 2, low, mid, left, right),
                   get(id * 2 + 1, mid + 1, high, left, right));
    }

   public:
    void init(int treeSize, int arr[]) {
        this->treeSize = treeSize;
        int tmp = 1;
        while (tmp < treeSize) {
            tmp *= 2;
        }
        nodes.resize(tmp * 2);
        leaf.resize(treeSize + 1);
        initTree(1, 1, treeSize, arr);
    }
    void update(int id, int value) {
        id = leaf[id];
        nodes[id] = value;
        while (id > 1) {
            id /= 2;
            nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
        }
    }
    int get(int left, int right) { return get(1, 1, treeSize, left, right); }
} smt;

int numCake, firstEat, numQuery, maxCake;
int cake[MAX_N];
int pos[15];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> numCake >> firstEat;
    maxCake = numCake;
    for (int i = 1; i <= numCake; i++) {
        cin >> cake[i];
    }
    smt.init(numCake, cake);
    for (int i = 1; i <= numCake; i++) {
        for (int j = 1; j <= 10; j++) {
            if (cake[i] > cake[pos[j]]) {
                for (int k = 10; k > j; k--) {
                    pos[k] = pos[k - 1];
                }
                pos[j] = i;
                break;
            }
        }
    }
    cin >> numQuery;
    while (numQuery--) {
        char type;
        cin >> type;
        if (type == 'E') {
            int p, e;
            cin >> p >> e;
            if (pos[e] == p) {
                continue;
            }
            int current = 10;
            for (int i = 10; i >= e; i--) {
                if (pos[i] == p) {
                    current = i;
                    break;
                }
            }
            for (int i = current; i > e; i--) {
                pos[i] = pos[i - 1];
            }
            pos[e] = p;
            for (int i = e; i > 1; i--) {
                cake[pos[i]] = cake[pos[i - 1]];
                smt.update(pos[i], cake[pos[i]]);
            }
            maxCake++;
            cake[pos[1]] = maxCake;
            smt.update(pos[1], maxCake);
        } else {
            int x;
            cin >> x;
            if (x == firstEat) {
                cout << 0 << '\n';
                continue;
            } else if (x < firstEat) {
                int maxSegment = smt.get(x, firstEat - 1);
                int low = firstEat, high = numCake;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (smt.get(firstEat + 1, mid) < maxSegment) {
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
                cout << high - x << '\n';
            } else {
                int maxSegment = smt.get(firstEat + 1, x);
                int low = 1, high = firstEat;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (smt.get(mid, firstEat - 1) < maxSegment) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                cout << x - low << '\n';
            }
        }
    }

    return 0;
}

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