| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 437803 |
2021-06-27T06:53:20 Z |
XBoRickie |
Game (IOI13_game) |
C++11 |
|
0 ms |
0 KB |
#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);
}
int main(int argc, char* argv[]) {
FastIO;
int r, c, n;
scanf("%d%d%d", &r, &c, &n);
init(r, c);
int type;
int p, q, u, v;
int64 k;
while(n--) {
scanf("%d", &type);
if (type == 1) {
scanf("%d%d", &p, &q);
p--; q--;
scanf("%I64d", &k);
update(p, q, k);
} else {
scanf("%d%d%d%d", &p, &q, &u, &v);
p--; q--; u--; v--;
printf("%I64d\n", calculate(p, q, u, v));
}
}
return 0;
}
Compilation message
game.cpp: In function 'int main(int, char**)':
game.cpp:488:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int64*' {aka 'long long int*'} [-Wformat=]
488 | scanf("%I64d", &k);
| ~~~~^ ~~
| | |
| | int64* {aka long long int*}
| int*
| %I64lld
game.cpp:493:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
493 | printf("%I64d\n", calculate(p, q, u, v));
| ~~~~^ ~~~~~~~~~~~~~~~~~~~~~
| | |
| int long long int
| %I64lld
game.cpp:477:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
477 | scanf("%d%d%d", &r, &c, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
game.cpp:484:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
484 | scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
game.cpp:486:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
486 | scanf("%d%d", &p, &q);
| ~~~~~^~~~~~~~~~~~~~~~
game.cpp:488:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
488 | scanf("%I64d", &k);
| ~~~~~^~~~~~~~~~~~~
game.cpp:491:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
491 | scanf("%d%d%d%d", &p, &q, &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccg61UFV.o: in function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgBcSrW.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccgBcSrW.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
