Submission #437804

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
437804	2021-06-27T06:54:25 Z	XBoRickie	Game (IOI13_game)	C++11	Compilation error	0 ms	0 KB

game

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

typedef long double             ld;
typedef long long int           int64;
typedef unsigned long long int  uint64;
typedef std::pair<int, int>          PII;
typedef std::vector<int>             VI;
typedef std::vector<long long>       VLL;
typedef std::vector<PII>             VII;
typedef std::vector<VI>              VVI;

#define FOR(i, j, k, in)        for (int i = (j); i < (k); i += (in))
#define FORW(i, j, k, in)       for (int i = (j); i <= (k); i += (in))
#define RFOR(i, j, k, in)       for (int i = (j); i >= (k); i -= (in))

#define all(cont)               cont.begin(), cont.end()
#define rall(cont)              cont.rbegin(), cont.rend()
#define sz(cont)                int((cont).size())
#define pb                      push_back
#define mp                      make_pair
#define fi                      first
#define se                      second

#define IINF                    0x3f3f3f3f
#define LLINF                   1000111000111000111LL
#define PI                      3.1415926535897932384626433832795

#define FastIO                  std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
#define hardio(name)            freopen(name".inp","r",stdin), freopen(name".out","w",stdout);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
const int MOD = 1e9 + 7;

int64 gcd(int64 a, int64 b) { return (a == 0 ? b : gcd(b % a, a)); }

struct Cell {
    int r, c;
    bool operator < (const Cell& o) const {
        return c < o.c || (c == o.c && r < o.r);
    }
    bool operator > (const Cell& o) const {
        return c > o.c || (c == o.c && r > o.r);
    }
    bool operator <= (const Cell& o) const {
        return c <= o.c || (c == o.c && r <= o.r);
    }
    bool operator >= (const Cell& o) const {
        return c >= o.c || (c == o.c && r >= o.r);
    }
    bool operator == (const Cell& o) const {
        return c == o.c && r == o.r;
    }
    bool operator != (const Cell &x) const {
        return c != x.c || r != x.r;
    }
};

class no_such_element_exception: public runtime_error {
public:
    no_such_element_exception(): runtime_error("No such element exists"){}
    no_such_element_exception(string message): runtime_error(message){}
};

template<typename Key = Cell, typename Value = uint64>
struct AVLTree {
    struct Node {
    public:
        Key key;
        Key maxKey;
        Key minKey;
        Value val;
        Value gcd;
        int height, size;
        Node *left = nullptr, *right = nullptr;
        Node(Key key_, Value val_, int height_, int size_) {
            key = key_;
            maxKey = key_; minKey = key_;
            val = val_; gcd = val_;
            height = height_; size = size_;
        }
    };

private:
    // Root node.
    Node *root = nullptr;

    // Return the number of nodes in the subtree.
    // @param x: The subtree
    // @return the number of nodes in the subtree
    int size(Node *&x) { if (x == nullptr) return 0; return x->size; }

    // Return the height in the subtree.
    // @param x: The subtree
    // @return the height in the subtree
    int height(Node *&x) { if (x == nullptr) return -1; return x->height; }

    // Update the size and height of the subtree.
    void update(Node *&x) {
        x->gcd = gcd(gcd(x->left ? x->left->gcd : 0LL, x->right ? x->right->gcd : 0LL), x->val);
        x->minKey = x->left ? x->left->minKey : x->key;
        x->maxKey = x->right ? x->right->maxKey : x->key;
        x->size = 1 + size(x->left) + size(x->right);
        x->height = 1 + max(height(x->left), height(x->right));
    }

    int balanceFactor(Node *&x) {
        return height(x->left) - height(x->right);
    }

    // Rotates the given subtree to the right.
    // @param x: The subtree
    // @return the right rotated subtree
    Node *rotateRight(Node *&x) {
        Node *y = x->left;
        x->left = y->right;
        y->right = x;
        update(x); update(y);
        return y;
    }


    // Rotates the given subtree to the left.
    // @param x: The subtree
    // @return the left rotated subtree
    Node *rotateLeft(Node *&x) {
        Node *y = x->right;
        x->right = y->left;
        y->left = x;
        update(x); update(y);
        return y;
    }

    // Restore the AVL tree property of the subtree.
    Node *balance(Node *&x) {
        if (balanceFactor(x) < -1) {
            if (balanceFactor(x->right) > 0) x->right = rotateRight(x->right);
            x = rotateLeft(x);
        } else if (balanceFactor(x) > 1) {
            if (balanceFactor(x->left) < 0) x->left = rotateLeft(x->left);
            x = rotateRight(x);
        }
        update(x);
        return x;
    }

    // Returns value associated with the given key in the subtree.
    Node *get(Node *&x, Key key) {
        if (x == nullptr) return nullptr;
        if (key < x->key) return get(x->left, key);
        else if (key > x->key) return get(x->right, key);
        else return x;
    }

    // Inserts the key-value pair in the subtree. It overrides the old value
    // with the new value if the symbol table already contains the specified key.
    Node *put(Node *&x, Key key, Value val) {
        if (x == nullptr) return new Node(key, val, 0, 1);
        if (key < x->key) x->left = put(x->left, key, val);
        else if (key > x->key) x->right = put(x->right, key, val);
        else {
            x->val = val;
            update(x);
            return x;
        }
        return balance(x);
    }

    Node *removeMin(Node *&x) {
        if (x->left == nullptr) return x->right;
        x->left = removeMin(x->left);
        return balance(x);
    }

    // Removes the largest value from the given subtree.
    Node *removeMax(Node *&x) {
        if (x->right == nullptr) return x->left;
        x->right = removeMax(x->right);
        return balance(x);
    }

    // Returns the node with the smallest value in the subtree.
    Node *getMin(Node *&x) {
        if (x->left == nullptr) return x;
        return getMin(x->left);
    }

    // Returns the node with the largest value in the subtree.
    Node *getMax(Node *&x) {
        if (x->right == nullptr) return x;
        return getMax(x->right);
    }

    // Removes the specified key and its associated value from the given subtree.
    Node *remove(Node *&x, Key key) {
        if (key < x->key) x->left = remove(x->left, key);
        else if (key > x->key) x->right = remove(x->right, key);
        else {
            if (x->left == nullptr) return x->right;
            else if (x->right == nullptr) return x->left;
            else {
                Node *y = x;
                x = getMin(y->right);
                x->right = removeMin(y->right);
                x->left = y->left;
            }
        }
        return balance(x);
    }

    // Returns the node in the subtree with the largest key less than or equal
    // to the given key
    Node *floor(Node *&x, Key key) {
        if (x == nullptr) return nullptr;
        if (key == x->key) return x;
        if (key < x->key) return floor(x->left, key);
        Node *y = floor(x->right, key);
        if (y != nullptr) return y;
        else return x;
    }

    // Returns the node in the subtree with the smallest key greater than or
    // equal to the given key.
    Node *ceiling(Node *&x, Key key) {
        if (x == nullptr) return nullptr;
        if (key == x->key) return x;
        if (key > x->key) return ceiling(x->right, key);
        Node *y = ceiling(x->left, key);
        if (y != nullptr) return y;
        else return x;
    }

    // Returns the node with value the kth smallest value in the subtree.
    Node *select(Node *&x, int k) {
        if (x == nullptr) return nullptr;
        int t = size(x->left);
        if (t > k) return select(x->left, k);
        else if (t < k) return select(x->right, k - t - 1);
        return x;
    }

    // Returns the number of keys in the subtree less than key.
    int rank(Key key, Node *&x) {
        if (x == nullptr) return 0;
        if (key < x->key) return rank(key, x->left);
        else if (key > x->key) return 1 + size(x->left) + rank(key, x->right);
        else return size(x->left);
    }


    // Adds the key-value pairs in the subtree to queue following an in-order traversal.
    void keyValuePairsInOrder(Node *&x, vector<pair<Key, Value>> *queue) {
        if (x == nullptr) return;
        keyValuePairsInOrder(x->left, queue);
        queue->push_back({x->key, x->val});
        keyValuePairsInOrder(x->right, queue);
    }

    //Adds the key-value pairs between {@code lo} and {@code hi} in the subtree
    //to the {@code queue}.
    void keyValuePairs(Node *&x, vector<pair<Key, Value>> *queue, Key lo, Key hi) {
        if (x == nullptr) return;
        if (lo < x->key) keyValuePairs(x->left, queue, lo, hi);
        if (lo <= x->key && hi >= x->key) queue->push_back({x->key, x->val});
        if (hi > x->key) keyValuePairs(x->right, queue, lo, hi);
    }

    long long query(Node *&x, Key lo, Key hi) {
        if (x == nullptr) return 0LL;
        if (lo <= x->minKey && hi >= x->maxKey) return x->gcd;
        if (hi < x->key) return query(x->left, lo, hi);
        if (lo > x->key) return query(x->right, lo, hi);
        return gcd(x->val, gcd(query(x->left, lo, x->left ? x->left->maxKey : hi), query(x->right, x->right ? x->right->minKey : lo, hi)));
    }

public:
    // Initializes an empty symbol table.
    AVLTree() {}

    // Checks if the symbol table is empty.
    bool isEmpty() { return root == nullptr; }

    // Returns the number key-value pairs in the symbol table.
    int size() { return size(root); }

    // Returns the height of the internal AVL tree. It is assumed that the
    // height of an empty tree is -1 and the height of a tree with just one node
    // is 0.
    int height() { return height(root); }

    // Returns the value associated with the given key.
    Value get(Key key) {
        no_such_element_exception("no such key is in the symbol table");
        Node *x = get(root, key);
        return x->val;
    }

    // Checks if the symbol table contains the given key.
    bool contains(Key key) {
        return get(root, key) != nullptr;
    }

    // Inserts the specified key-value pair into the symbol table, overwriting
    // the old value with the new value if the symbol table already contains the
    // specified key.
    void put(Key key, Value val) { root = put(root, key, val); }

    // Removes the specified key and its associated value from the symbol table
    // (if the key is in the symbol table).
    void remove(Key key) {
        if (!contains(key)) return;
        root = remove(root, key);
    }

    // Removes the smallest value from the symbol table.
    void removeMin() {
        if (isEmpty()) throw runtime_error("called removeMin() with empty symbol table");
        root = removeMin(root);
    }

    // Removes the largest value from the symbol table.
    void removeMax() {
        if (isEmpty()) throw runtime_error("called removeMax() with empty symbol table");
        root = deleteMax(root);
    }

    // Returns the smallest key in the symbol table and its associated value.
    pair<Key, Value> getMin() {
        if (isEmpty()) throw runtime_error("called getMin() with empty symbol table");
        Node *x = getMin(root);
        return {x->key, x->val};
    }

    // Returns the largest key in the symbol table and its associated value.
    pair<Key, Value> getMax() {
        if (isEmpty()) throw runtime_error("called getMax() with empty symbol table");
        Node *x = getMax(root);
        return {x->key, x->val};
    }

    // Returns the largest key in the symbol table less than or equal to {@code key} and its associated value.
    pair<Key, Value> floor(Key key) {
        if (isEmpty()) throw runtime_error("called floor() with empty symbol table");
        Node *x = floor(root, key);
        if (x == nullptr) throw no_such_element_exception("call to floor() resulted in no such value");
        return {x->key, x->val};
    }

    // Returns the smallest key in the symbol table greater than or equal to {@code key} and its associated value.
    pair<Key, Value> ceiling(Key key) {
        if (isEmpty()) throw runtime_error("called ceiling() with empty symbol table");
        Node *x = ceiling(root, key);
        if (x == nullptr) throw no_such_element_exception("call to ceiling() resulted in no such value");
        return {x->key, x->val};
    }

    // Returns the kth smallest key in the symbol table and its associated value.
    pair<Key, Value> select(int k) {
        if (k < 0 || k >= size()) throw invalid_argument("k is not in range 0 to size");
        Node *x = select(root, k);
        return {x->key, x->val};
    }

    // Returns the number of keys in the symbol table strictly less than
    // {@code key}.
    int rank(Key key) {
        return rank(key, root);
    }

    // Returns all key-value pairs in the symbol table following an in-order traversal.
    vector<pair<Key, Value>> keyValuePairs() {
        vector<pair<Key, Value>> queue;
        keyValuePairsInOrder(root, &queue);
        return queue;
    }

    // Returns all key-value pairs in the symbol table in the given range.
    vector<pair<Key, Value>> keyValuePairs(Key lo, Key hi) {
        vector<pair<Key, Value>> queue;
        keyValuePairs(root, &queue, lo, hi);
        return queue;
    }

    long long query(Key lo, Key hi) {
        return query(root, lo, hi);
    }

    // Returns the number of keys in the symbol table in the given range.
    int size(Key lo, Key hi) {
        if (lo > hi) return 0;
        if (contains(hi)) return rank(hi) - rank(lo) + 1;
        else return rank(hi) - rank(lo);
    }
};

struct DynamicSegmentTree {
    struct Node {
    public:
        Node *up = nullptr, *down = nullptr;
        AVLTree<Cell, long long> *rowTree = nullptr;
    };

private:
    Node *root;
    int R; // number of rows
    int C; // number of columns

    void update(Node *cur, int cU, int cD, int rowInd, int colInd, long long val) {
        if (cU > rowInd || cD < rowInd) return;
        if (cur->rowTree == nullptr) cur->rowTree = new AVLTree<Cell, long long>();
        cur->rowTree->put({rowInd, colInd}, val);
        if (cU >= rowInd && cD <= rowInd) return;
        int m = cU + (cD - cU) / 2;
        if (rowInd <= m) {
           if (cur->up == nullptr) cur->up = new Node();
           update(cur->up, cU, m, rowInd, colInd, val);
        } else {
           if (cur->down == nullptr) cur->down = new Node();
           update(cur->down, m + 1, cD, rowInd, colInd, val);
        }
    }

    long long query(Node *cur, int cU, int cD, int u, int l, int d, int r) {
        if (cur == nullptr || cU > d || cD < u) return 0LL;
        if (cU >= u && cD <= d) {
            if (cur->rowTree == nullptr) return 0LL;
            return cur->rowTree->query({u, l}, {d, r});
        }
        int m = cU + (cD - cU) / 2;
        if (d <= m) return query(cur->up, cU, m, u, l, d, r);
        else if (u > m) return query(cur->down, m + 1, cD, u, l, d, r);
        long long up = query(cur->up, cU, m, u, l, m, r);
        long long down = query(cur->down, m + 1, cD, m + 1, l, d, r);
        return gcd(up, down);
    }

public:
    DynamicSegmentTree(int rows, int cols) {
        root = new Node();
        R = rows;
        C = cols;
    }

    void update(int rowInd, int colInd, long long val) {
        update(root, 1, R, rowInd, colInd, val);
    }

    long long query(int u, int l, int d, int r) {
        return query(root, 1, R, u, l, d, r);
    }

    int rows() {
        return R;
    }

    int cols() {
        return C;
    }
} *st;

void init(int R, int C) {
    st = new DynamicSegmentTree(R, C);
}

void update(int P, int Q, long long K) {
    st->update(P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st->query(P + 1, Q + 1, U + 1, V + 1);
}

Compilation message

/usr/bin/ld: /tmp/cczyi6Mo.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status