#include <bits/stdc++.h>
#include "game.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
typedef long long ll;
typedef pair < ll , ll > ii;
ll gcd(ll X, ll Y) {
if(X == 0 || Y == 0) {
return X + Y;
}
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll n, m, k;
struct node{
ll key, pri, L, R, val, top;
}a[MAXN];
ll yeniver(ll x, ll y){
k++;
a[k].key = x;
a[k].val = a[k].top = y;
a[k].L = a[k].R = 0;
a[k].pri = rand() >> 16 ^ rand();
return k;
}
void bal(ll T){
if(!T)return;
a[T].top = gcd(a[T].val, gcd(a[a[T].L].top, a[a[T].R].top));
}
void split(ll T, ll ky, ll &L, ll &R){
if(!T)
L = R = 0;
else if(a[T].key > ky)
split(a[T].L, ky, L, a[T].L), R = T;
else
split(a[T].R, ky, a[T].R, R), L = T;
bal(L);
bal(R);
}
void merge(ll &T, ll L, ll R){
if(!L or !R)
T = max(L, R);
else if(a[L].pri > a[R].pri)
merge(a[L].R, a[L].R, R), T = L;
else
merge(a[R].L, L, a[R].L), T = R;
bal(T);
}
void insert(ll &T, ll p){
if(!T)
T = p;
else if(a[p].pri > a[T].pri)
split(T, a[p].key, a[p].L, a[p].R), T = p;
else
insert((a[p].key < a[T].key) ? a[T].L : a[T].R, p);
bal(T);
}
void erase(ll &T, ll ky){
if(!T)
T = 0;
else if(a[T].key == ky)
merge(T, a[T].L, a[T].R);
else if(a[T].key > ky)
erase(a[T].L, ky);
else
erase(a[T].R, ky);
bal(T);
}
ll topver(ll T, ll bas, ll son){
ll bir, iki, uc;
split(T, son, iki, uc);
split(iki, bas - 1, bir, iki);
ll don = a[iki].top;
merge(T, bir, iki);
merge(T, T, uc);
return don;
}
ll root = 0, say, seg[4*MAXN], sol[4*MAXN], sag[4*MAXN];
ll solver(ll k){return (sol[k])?sol[k]:sol[k] = ++say;}
ll sagver(ll k){return (sag[k])?sag[k]:sag[k] = ++say;}
void up(ll k, ll bas, ll son, ll x, ll y, ll z){
erase(seg[k], y);
insert(seg[k], yeniver(y, z));
if(bas == son)
return;
if(x <= orta)
up(solver(k), bas, orta, x, y, z);
else
up(sagver(k), orta + 1, son, x, y, z);
}
ll qu(ll k, ll bas, ll son, ll x, ll y, ll xx, ll yy){
if(!k or bas > y or son < x)
return 0;
if(bas >= x and son <= y)
return topver(seg[k], xx, yy);
return gcd(qu(sol[k], bas, orta, x, y, xx, yy), qu(sag[k], orta + 1, son, x, y, xx, yy));
}
void init(int R, int C) {
srand(time(0));
n = R;m = C;
say++;
}
void update(int p, int q, int k) {
up(1, 1, n, p + 1, q + 1, k);
}
ll calculate(int p, int q, int u, int v) {
return qu(1, 1, n, p+1, u+1, q+1, v+1);
}
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;
^~~
/tmp/ccDTyxEL.o: In function `main':
grader.c:(.text.startup+0x122): undefined reference to `update'
collect2: error: ld returned 1 exit status
