// IOI 2013 - Game
// Lúcio Cardoso
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
int n, m;
struct Node {
int w, ind;
uint_fast64_t v, g;
Node *l, *r;
Node() {
l = r = NULL;
v = 0, g = 0, ind = -1;
w = rand();
}
};
typedef Node*& node_t;
struct Node2d {
Node *f;
Node2d *l, *r;
Node2d() {
f = NULL;
l = r = NULL;
}
};
Node2d *root = new Node2d;
ll gcd(ll X, ll Y)
{
uint_fast64_t tmp;
while (X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll get(Node *t)
{
if (!t) return 0;
return t->g;
}
void operation(Node *t)
{
if (!t) return;
t->g = gcd( gcd(t->v, get(t->l)), get(t->r));
}
uint_fast64_t find(node_t t, int v, ll k)
{
if (!t) return -1LL;
if (t->ind == v)
{
if (k != -1) t->v = k, operation(t);
return t->v;
}
else if (t->ind > v)
{
ll x = find(t->l, v, k);
if (x != -1 && k != -1) operation(t);
return x;
}
else
{
ll x = find(t->r, v, k);
if (x != -1 && k != -1) operation(t);
return x;
}
}
void split(Node *t, node_t l, node_t r, int pos)
{
if (!t) return void(l=r=NULL);
if (pos < t->ind)
split(t->l, l, t->l, pos), r = t;
else
split(t->r, t->r, r, pos), l = t;
operation(t);
}
void merge(node_t t, Node *l, Node *r)
{
if (l == NULL)
t = r;
else if (r == NULL)
t = l;
else if (l->w >= r->w)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
operation(t);
}
void upd_y(node_t t, Node *left, Node *right, int pos, ll v)
{
Node *tl = NULL, *tm = NULL, *tr = NULL;
uint_fast64_t vl = find(left, pos, -1), vr = find(right, pos, -1);
if (vl != -1) v = gcd(vl, v);
if (vr != -1) v = gcd(vr, v);
uint_fast64_t x = find(t, pos, v);
if (x == -1)
{
Node *aux = new Node;
aux->v = v, aux->ind = pos, aux->g = v;
split(t, tl, tr, pos-1);
merge(tl, tl, aux);
merge(t, tl, tr);
}
}
void upd_x(Node2d *nx, int lx, int rx, int x, int y, ll v)
{
if (lx != rx)
{
int mx = (lx+rx)/2;
if (x <= mx)
{
if (nx->l == NULL) nx->l = new Node2d;
upd_x(nx->l, lx, mx, x, y, v);
}
else
{
if (nx->r == NULL) nx->r = new Node2d;
upd_x(nx->r, mx+1, rx, x, y, v);
}
}
upd_y(nx->f, (nx->l==NULL)?NULL:nx->l->f, (nx->r==NULL)?NULL:nx->r->f, y, v);
}
uint_fast64_t query_y(node_t t, int l, int r)
{
if (!t) return 0;
Node *tl = NULL, *tm = NULL, *tr = NULL;
split(t, tl, tm, l-1);
split(tm, t, tr, r);
uint_fast64_t ans = 0;
if (t) ans = t->g;
merge(tm, tl, t);
merge(t, tm, tr);
return ans;
}
uint_fast64_t query_x(Node2d *nx, int tlx, int trx, int lx, int rx, int ly, int ry)
{
if (nx == NULL || lx > rx) return 0;
if (tlx == lx && trx == rx) return query_y(nx->f, ly, ry);
int mx = (tlx+trx)/2;
ll p1 = query_x(nx->l, tlx, mx, lx, min(rx, mx), ly, ry);
ll p2 = query_x(nx->r, mx+1, trx, max(lx, mx+1), rx, ly, ry);
return gcd(p1, p2);
}
void init(int R, int C)
{
n = R, m = C;
return;
}
void update(int P, int Q, long long K)
{
upd_x(root, 0, n-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return query_x(root, 0, n-1, P, U, Q, V);
}
int main(){}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
game.cpp: In function 'void upd_y(node_t, Node*, Node*, int, ll)':
game.cpp:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (vl != -1) v = gcd(vl, v);
~~~^~~~~
game.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (vr != -1) v = gcd(vr, v);
~~~^~~~~
game.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x == -1)
~~^~~~~
game.cpp:113:23: warning: unused variable 'tm' [-Wunused-variable]
Node *tl = NULL, *tm = NULL, *tr = NULL;
^~
/tmp/ccHgHqie.o: In function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc90znRQ.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
