#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
static int R, C;
struct X_NODE{
X_NODE(int s, int e): s(s), e(e), left(NULL), right(NULL), value(0LL){}
int s, e;
X_NODE *left, *right;
ll value;
};
struct Y_NODE{
Y_NODE(): left(NULL), right(NULL), xtree(1, C){}
Y_NODE *left, *right;
X_NODE xtree;
} *root;
ll gcd2(ll x, ll y){
if(y == 0) return x;
return gcd2(y, x%y);
}
void init(int r, int c){
R = r, C = c;
root = new Y_NODE();
}
void upd2(X_NODE *node, int q, ll val){
int s = node->s, e = node->e, m = (s+e)/2;
if(s == e){
node->value = val;
return;
}
X_NODE **child = &(q <= m ? node->left : node->right);
if(*child == NULL){
*child = new X_NODE(q, q);
(*child)->value = val;
}else if((*child)->s <= q && q<=(*child)->e){
upd2(*child, q, val);
}else{
do{
if(q <= m) e = m;
else s = m+1;
m = (s+e)/2;
}while((q<=m) == ((*child)->e <= m));
X_NODE *nnode = new X_NODE(s, e);
if((*child)->e <= m) nnode->left = *child;
else nnode->right = *child;
*child = nnode;
upd2(*child, q, val);
}
node->value = gcd2(
node->left? node->left->value:0,
node->right? node->right->value: 0
);
}
ll qry2(X_NODE *node, int s, int e){
if(node == NULL || node->s > e || node->e < s) return 0;
if(s <= node->s && node -> e <= e){
return node->value;
}
return gcd2(qry2(node->left, s, e), qry2(node->right, s, e));
}
void upd1(Y_NODE *node, int s, int e, int p, int q, ll val){
int m = (s+e)/2;
if(s == e){
upd2(&node->xtree, q, val);
return;
}
if(p<=m){
if(node->left == NULL) node->left = new Y_NODE();
upd1(node->left, s, m, p, q, val);
}else{
if(node->right == NULL) node->right = new Y_NODE();
upd1(node->right, m+1, e, p, q, val);
}
ll v = gcd2(
node->left?qry2(&node->left->xtree, q, q) : 0,
node->right?qry2(&node->right->xtree, q, q) : 0
);
upd2(&node->xtree, q, v);
}
void upd(int p, int q, ll val){
++p, ++q;
upd1(root, 1, R, p, q, val);
}
ll qry1(Y_NODE *node, int s, int e, int p, int q, int u, int v){
if(node == NULL || s > u || e < p) return 0;
if(p <= s && e <= u) return qry2(&node->xtree, q, v);
int m = (s+e) / 2;
return gcd2(
qry1(node->left, s, m, p, q, u, v),
qry1(node->right, m+1, e, p, q, u, v)
);
}
ll calculate(int p, int q, int u, int v){
++p, ++q, ++u, ++v;
return qry1(root, 1, R, p, q, u, v);
}
Compilation message
/usr/bin/ld: /tmp/ccXFfeZZ.o: in function `main':
grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status
