Submission #873757

#	Time	Username	Problem	Language	Result	Execution time	Memory
873757		thuanqvbn03	Cake (CEOI14_cake)	C++17	0 / 100	994 ms	38828 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;
    Node(int label = 0) {
        parent = children[0] = children[1] = NULL;
        this->label = label;
        treeSize = 1;
    }
    int getDir(Node *a) { return (a == children[0] ? 0 : 1); }
    void pushUp() {
        treeSize = 1;
        for (int i = 0; i < 2; i++) {
            treeSize += (children[i] == NULL ? 0 : children[i]->treeSize);
        }
    }
};

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

struct SplayTree {
    Node *root;
    SplayTree(Node *node = NULL) {
        root = node;
        if (root != NULL) {
            root->parent = NULL;
        }
    }
    void link(Node *a, Node *b, int dir) {
        if (a == NULL) {
            root = b;
            if (root != NULL) {
                root->parent = NULL;
            }
            return;
        }
        a->children[dir] = b;
        if (b != NULL) {
            b->parent = a;
        }
    }
    void rotate(Node *a, int dir) {
        Node *b = a->children[dir];
        Node *p = a->parent;
        int parDir = (p == NULL ? 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 != NULL) {
            int dir = a->parent->getDir(a);
            if (a->parent->parent == NULL) {
                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];
            }
        }
    }
    int getPos(Node *p) {
        splay(p);
        return treeSize(root->children[0]) + 1;
    }
    void merge(SplayTree other) {
        if (other.root == NULL) {
            return;
        }
        if (root == NULL) {
            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 = NULL;
            return SplayTree(tmp);
        }
        find(pos - 1);
        Node *tmp = root->children[1];
        root->children[1] = NULL;
        tmp->parent = NULL;
        root->pushUp();
        return SplayTree(tmp);
    }
    Node *insert(int label) {
        Node *tmp = new Node(label);
        merge(SplayTree(tmp));
        return tmp;
    }
    void moveTree(int from, int to) {
        SplayTree tmp = split(from + 1);
        SplayTree subtree = split(from);
        merge(tmp);
        tmp = split(to - 1);
        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;
};

struct FenwickTree {
    int treeSize, logTreeSize;
    vector<int> nodes;
    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
        logTreeSize = log2(treeSize) + 1;
    }
    void update(int id, int val) {
        for (; id <= treeSize; id += (id & -id)) {
            nodes[id] += val;
        }
    }
    int get(int id) {
        int result = 0;
        for (; id >= 1; id -= (id & -id)) {
            result += nodes[id];
        }
        return result;
    }
    int lifting(int value) {
        int sum=0, pos = 0;
        
        for (int i = logTreeSize; i >= 0; i--) {
            if (pos + (1 << i) <= treeSize &&
                sum + nodes[pos + (1 << i)] < value) {
                pos += (1 << i);
                sum += nodes[pos];
            }
        }
        return pos + 1;
    }
} ft;

int numCake, firstEat, numQuery, maxCake;
int cake[MAX_N];
SplayTree splayTree;
Query queries[MAX_N];
Node *nodes[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(NULL);
    for (auto &[u, v] : tmp) {
        nodes[v] = splayTree.insert(v);
    }
}

void buildCurrentRate() {
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 'E') {
            queries[i].u = splayTree.getPos(nodes[queries[i].pos]);
            queries[i].v = numCake - queries[i].v + 1;
            splayTree.moveTree(queries[i].u, queries[i].v);
        }
    }
}

void buildTarget() {
    ft.init(numCake + numQuery);
    for (int i = 1; i <= numCake; i++) {
        ft.update(i, 1);
    }
    int maxValue = numCake;
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 'E') {
            maxValue++;
            queries[i].u = ft.lifting(queries[i].u);
            ft.update(queries[i].u, -1);
            ft.update(maxValue, 1);
        }
    }
    for (int i = numQuery; i >= 1; i--) {
        if (queries[i].type == 'E') {
            queries[i].v = ft.lifting(queries[i].v);
            ft.update(queries[i].u, 1);
            ft.update(queries[i].v, -1);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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();
    buildCurrentRate();
    buildTarget();
    for (int i = 1; i <= numCake; i++)
    {
        cake[i] = ft.lifting(cake[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);
        } 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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50