#include <iostream>
#include <utility>
#define LL long long
#define MAXN 22005
using namespace std;
LL gcd(LL X, LL Y) {
LL tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
//begin treap
struct Node {
LL GCD, val; //gcd of subtree
int c, pri, l, r; //column, priority, children
};
class TreapForest {
public:
Node trp[MAXN * 125];
int ptr = 1;
void pushup(int t) {
trp[t].GCD = gcd(gcd(trp[trp[t].l].GCD, trp[trp[t].r].GCD), trp[t].val);
}
int addnode(LL v, int c) { //can also be used to make new treap in forest
trp[ptr].val = trp[ptr].GCD = v;
trp[ptr].pri = rand();
trp[ptr].c = c;
return(ptr++); //return node index
}
void Split(int t, int &l, int &r, int val) {
//split subtree t so c <= val to l, c > val to r
if (!t) {
l = r = 0;
return;
} else if (trp[t].c > val) {
Split(trp[t].l, l, trp[t].l, val);
r = t;
} else {
Split(trp[t].r, trp[t].r, r, val);
l = t;
}
pushup(t);
}
void Merge(int &t, int l, int r) {
//maxC(l) <= maxC(r)
//combine subtrees l, r into pointer t
if (!l || !r) {
t = max(l, r);
return;
} else if (trp[l].pri < trp[r].pri) { //bigger pri on top
Merge(trp[r].l, l, trp[r].l);
t = r;
} else {
Merge(trp[l].r, trp[l].r, r);
t = l;
}
pushup(t);
}
int Insert(int rt, LL val, int c) {
int NewNode = addnode(val, c); //assume rt does not already have key c
int l, r;
Split(rt, l, r, c);
Merge(l, l, NewNode);
Merge(r, l, r);
return(r); //new root
}
int Del(int rt, int c) { //Delete if exists
int l, r, trash;
Split(rt, l, r, c);
Split(l, l, trash, c-1);
Merge(r, l, r);
return(r);
}
pair <LL,int> Ask(int rt, int lo, int hi) { //range query
int l, mid, r;
LL res;
Split(rt, l, mid, lo-1);
Split(mid, mid, r, hi);
res = trp[mid].GCD;
Merge(mid, mid, r);
Merge(l, l, mid);
return(pair <LL,int> {res, l});
}
} Treap;
//end treap begin segtree
class LazyCreate {
int ST[MAXN * 125]; //store treap root, order by rows
int L[MAXN * 125], R[MAXN * 125], ptr = 2;
public:
void addnode(int par) {
L[par] = ptr++;
R[par] = ptr++;
}
void modify(int cur, LL val, int c) {
if (!ST[cur]) {
ST[cur] = Treap.addnode(val, c);
} else {
ST[cur] = Treap.Del(ST[cur], c);
ST[cur] = Treap.Insert(ST[cur], val, c);
}
}
LL upd(int r, int c, LL val, int Rl, int Rr, int cur) {
if (r < Rl || r > Rr) {
pair <LL,int> ret = Treap.Ask(ST[cur],c,c);
ST[cur] = ret.second;
return(ret.first);
} else if (Rl == Rr) {
modify(cur, val, c);
return(val);
} else {
if (!L[cur]) {addnode(cur);}
int mid = (Rl + Rr) >> 1;
LL a = upd(r, c, val, Rl, mid, L[cur]);
LL b = gcd(a, upd(r, c, val, mid+1, Rr, R[cur]));
modify(cur, b, c);
return(b);
}
}
LL ask(int Lr, int Hr, int Lc, int Hc, int Rl, int Rr, int cur) {
if (Hr < Rl || Lr > Rr || !cur) {return(0);}
else if (Lr <= Rl && Hr >= Rr) {
pair <LL,int> ret = Treap.Ask(ST[cur],Lc, Hc);
ST[cur] = ret.second;
return(ret.first);
} else {
int mid = (Rl + Rr) >> 1;
return(gcd( ask(Lr, Hr, Lc, Hc, Rl, mid, L[cur]),
ask(Lr, Hr, Lc, Hc, mid+1, Rr, R[cur])));
}
}
} ST;
int R,C;
void init(int r, int c) {
R = r, C = c;
}
void update(int P, int Q, long long K) {
ST.upd(P,Q,K, 0, R-1, 1);
}
long long calculate(int P, int Q, int U, int V) {
return(ST.ask(P,U,Q,V,0, R-1, 1));
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
/tmp/ccm5CM6L.o: In function `main':
grader.c:(.text.startup+0x5d): undefined reference to `init'
grader.c:(.text.startup+0xb8): undefined reference to `calculate'
grader.c:(.text.startup+0x122): undefined reference to `update'
collect2: error: ld returned 1 exit status
