oj.uz

답안 #874456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874456 2023-11-17T04:47:24 Z thuanqvbn03 케이크 (CEOI14_cake) C++17
100 / 100
 1175 ms 53540 KB 
// 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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 5 ms 6780 KB Output is correct
5 Correct 16 ms 7360 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 44928 KB Output is correct
2 Correct 189 ms 45260 KB Output is correct
3 Correct 303 ms 44980 KB Output is correct
4 Correct 160 ms 45136 KB Output is correct
5 Correct 409 ms 48152 KB Output is correct
6 Correct 323 ms 48000 KB Output is correct
7 Correct 326 ms 48236 KB Output is correct
8 Correct 171 ms 48004 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 21556 KB Output is correct
2 Correct 157 ms 21580 KB Output is correct
3 Correct 152 ms 21472 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 366 ms 30244 KB Output is correct
6 Correct 443 ms 30296 KB Output is correct
7 Correct 278 ms 30172 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 10144 KB Output is correct
2 Correct 61 ms 10104 KB Output is correct
3 Correct 153 ms 17792 KB Output is correct
4 Correct 119 ms 17792 KB Output is correct
5 Correct 140 ms 16732 KB Output is correct
6 Correct 281 ms 25252 KB Output is correct
7 Correct 210 ms 18468 KB Output is correct
8 Correct 214 ms 32428 KB Output is correct
9 Correct 1175 ms 53404 KB Output is correct
10 Correct 457 ms 33928 KB Output is correct
11 Correct 605 ms 35492 KB Output is correct
12 Correct 1074 ms 50816 KB Output is correct
13 Correct 1028 ms 53540 KB Output is correct