Submission #874456

#	Time	Username	Problem	Language	Result	Execution time	Memory
874456		thuanqvbn03	Cake (CEOI14_cake)	C++17	100 / 100	1175 ms	53540 KiB

cake

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

using namespace std;

const int MAX_N = 500005;

struct Node {
    Node *parent, *children[2];
    int label;
    int treeSize;
    int weight;
    int sumWeight;
    Node(int label = 0) {
        parent = children[0] = children[1] = nullptr;
        this->label = label;
        treeSize = 1;
        weight = 1;
        sumWeight = 1;
    }
    int getDir(Node *a) { return (a == children[0] ? 0 : 1); }
    void pushUp() {
        treeSize = 1;
        sumWeight = weight;
        for (int i = 0; i < 2; i++) {
            treeSize += (children[i] == nullptr ? 0 : children[i]->treeSize);
            sumWeight += (children[i] == nullptr ? 0 : children[i]->sumWeight);
        }
    }
};

int treeSize(Node *p) { return (p == nullptr ? 0 : p->treeSize); }
int sumWeight(Node *p) { return (p == nullptr ? 0 : p->sumWeight); }

struct SplayTree {
    Node *root;
    SplayTree(Node *node = nullptr) {
        root = node;
        if (root != nullptr) {
            root->parent = nullptr;
        }
    }
    void link(Node *a, Node *b, int dir) {
        if (a == nullptr) {
            root = b;
            if (root != nullptr) {
                root->parent = nullptr;
            }
            return;
        }
        a->children[dir] = b;
        if (b != nullptr) {
            b->parent = a;
        }
    }
    void rotate(Node *a, int dir) {
        Node *b = a->children[dir];
        Node *p = a->parent;
        int parDir = (p == nullptr ? 0 : p->getDir(a));
        link(a, b->children[dir ^ 1], dir);
        link(b, a, dir ^ 1);
        link(p, b, parDir);
    }
    void splay(Node *a) {
        while (a->parent != nullptr) {
            int dir = a->parent->getDir(a);
            if (a->parent->parent == nullptr) {
                rotate(a->parent, dir);
                a->children[dir ^ 1]->pushUp();
            } else {
                int parDir = a->parent->parent->getDir(a->parent);
                if (parDir == dir) {
                    rotate(a->parent->parent, parDir);
                    rotate(a->parent, dir);
                    a->children[dir ^ 1]->children[parDir ^ 1]->pushUp();
                    a->children[dir ^ 1]->pushUp();
                } else {
                    rotate(a->parent, dir);
                    rotate(a->parent, parDir);
                    for (int i = 0; i < 2; i++) {
                        a->children[i]->pushUp();
                    }
                }
            }
            a->pushUp();
        }
    }
    void find(int pos) {
        Node *p = root;
        while (true) {
            int left = treeSize(p->children[0]);
            int mid = 1;
            if (left >= pos) {
                p = p->children[0];
            } else if (left + mid >= pos) {
                return splay(p);
            } else {
                pos -= left + mid;
                p = p->children[1];
            }
        }
    }
    void findWeight(int pos) {
        Node *p = root;
        while (true) {
            int left = sumWeight(p->children[0]);
            int mid = (p->weight);
            if (left >= pos) {
                p = p->children[0];
            } else if (left + mid >= pos) {
                return splay(p);
            } else {
                pos -= left + mid;
                p = p->children[1];
            }
        }
    }
    int getPos(Node *p) {
        splay(p);
        return treeSize(root->children[0]) + 1;
    }
    int getWeight(Node *p) {
        splay(p);
        return sumWeight(root->children[0]) + p->weight;
    }
    void merge(SplayTree other) {
        if (other.root == nullptr) {
            return;
        }
        if (root == nullptr) {
            root = other.root;
            return;
        }
        find(treeSize(root));
        link(root, other.root, 1);
        root->pushUp();
    }
    SplayTree split(int pos) {
        if (pos > treeSize(root)) {
            return SplayTree();
        }
        if (pos == 1) {
            Node *tmp = root;
            root = nullptr;
            return SplayTree(tmp);
        }
        find(pos - 1);
        Node *tmp = root->children[1];
        root->children[1] = nullptr;
        tmp->parent = nullptr;
        root->pushUp();
        return SplayTree(tmp);
    }
    Node *insert(int label) {
        Node *tmp = new Node(label);
        merge(SplayTree(tmp));
        return tmp;
    }
    void insert(SplayTree tree, int pos) {
        findWeight(pos - 1);
        SplayTree tmp = split(getPos(root) + 1);
        merge(tree);
        merge(tmp);
    }
    void moveTree(int from, int to) {
        SplayTree tmp = split(from + 1);
        SplayTree subtree = split(from);
        merge(tmp);
        tmp = split(to);
        merge(subtree);
        merge(tmp);
    }
    int query(int pos) {
        find(pos);
        return root->label;
    }
};

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;

struct Query {
    char type;
    int pos, u, v;
    Node *uNode, *vNode;
};

int numCake, firstEat, numQuery, maxCake;
int cake[MAX_N];
SplayTree splayTree;
Query queries[MAX_N];
Node *nodes[MAX_N], *initNode[MAX_N];

void buildSplayTree() {
    vector<pair<int, int>> tmp(numCake);
    for (int i = 1; i <= numCake; i++) {
        tmp[i - 1] = make_pair(cake[i], i);
    }
    sort(tmp.begin(), tmp.end());
    splayTree = SplayTree(nullptr);
    for (auto &[u, v] : tmp) {
        nodes[v] = initNode[v] = splayTree.insert(v);
    }
}

void buildQuery() {
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 'E') {
            queries[i].uNode = nodes[queries[i].pos];
            splayTree.getWeight(queries[i].uNode);
            splayTree.root->weight = 0;
            splayTree.root->pushUp();
            queries[i].v = numCake - queries[i].v + 1;
            SplayTree tmp = SplayTree();
            nodes[queries[i].pos] = queries[i].vNode =
                tmp.insert(queries[i].pos);
            splayTree.insert(tmp, queries[i].v);
        }
    }
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 'E') {
            queries[i].u = splayTree.getPos(queries[i].uNode);
            queries[i].v = splayTree.getPos(queries[i].vNode);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("test.txt", "w", stdout);
#endif
    cin >> numCake >> firstEat;
    maxCake = numCake;
    for (int i = 1; i <= numCake; i++) {
        cin >> cake[i];
    }
    cin >> numQuery;
    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].type;
        if (queries[i].type == 'E') {
            cin >> queries[i].pos >> queries[i].v;
        } else {
            cin >> queries[i].pos;
        }
    }
    buildSplayTree();
    buildQuery();
    for (int i = 1; i <= numCake; i++) {
        cake[i] = splayTree.getPos(initNode[i]);
    }
    smt.init(numCake, cake);
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 'E') {
            smt.update(queries[i].pos, queries[i].v);
            cake[queries[i].pos] = queries[i].v;
        } else {
            if (queries[i].pos == firstEat) {
                cout << 0 << '\n';
                continue;
            } else if (queries[i].pos < firstEat) {
                int maxSegment = smt.get(queries[i].pos, 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 - queries[i].pos << '\n';
            } else {
                int maxSegment = smt.get(firstEat + 1, queries[i].pos);
                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 << queries[i].pos - low << '\n';
            }
        }
    }
    return 0;
}

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