#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
using ll = long long;
constexpr int MAXN = 5 + 2000;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
struct segtree {
#define m ((s+e)/2)
struct Node {
ll val;
Node* l, *r;
Node() : val(0), l(nullptr), r(nullptr) {}
};
Node* root = new Node();
segtree() = default;
ll query(int s, int e, Node* curr, int l, int r) {
if (l > r || curr == nullptr) return 0;
if (s == l && e == r) return curr->val;
return gcd(query(s, m, curr->l, l, min(m,r)), query(1+m, e, curr->r, max(1+m,l), r));
}
void update(int s, int e, Node* curr, int l, int r, ll add) {
if (l > r) return;
if (s == l && e == r) {
curr->val = add;
} else {
if (curr->l == nullptr) curr->l = new Node();
if (curr->r == nullptr) curr->r = new Node();
update(s, m, curr->l, l, min(m,r), add);
update(1+m, e, curr->r, max(1+m,l), r, add);
curr->val = gcd(curr->l->val, curr->r->val);
}
}};
namespace input {int R,C;}
namespace stree2d {
segtree t[4*MAXN];
ll query(int s, int e, int p, int l, int r, int sy, int ey) {
if (l > r) return 0;
if (s == l && e == r) return t[p].query(1, input::C, t[p].root, sy, ey);
ll le = query(s, m, 2*p, l, min(m,r), sy, ey);
ll ri = query(1+m, e, 1+2*p, max(1+m,l), r, sy, ey);
return gcd(le,ri);
}
void update(int s, int e, int p, int l, int r, int sy, int ey, ll add) {
if (l > r) return;
if (s == l && e == r) {
t[p].update(1, input::C, t[p].root, sy, ey, add);
} else {
update(s, m, 2*p, l, min(m,r), sy, ey, add);
update(1+m, e, 1+2*p, max(1+m,l), r, sy, ey, add);
ll newval = gcd(t[2*p].query(1, input::C, t[2*p].root, sy, ey),
t[1+2*p].query(1, input::C, t[1+2*p].root, sy, ey));
t[p].update(1, input::C, t[p].root, sy, sy, newval);
}
}}
int subtask=-1;
void init(int R, int C) {
if (R <= 10 && C <= 100000) { // subtask 2.
subtask = 2;
} else { // subtask 1 & 3.
subtask = 3;
}
input::R = R;
input::C = C;
}
segtree s2[11];
void update(int P, int Q, long long K) {
if (subtask == -1) return;
++P; ++Q;
if (subtask == 2) { // 10 segment trees.
s2[P].update(1, input::C, s2[P].root, Q, Q, K);
} else { // un solo segtree 2d.
assert(subtask == 3);
stree2d::update(1, input::R, 1, P, P, Q, Q, K);
}
}
long long calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
if (subtask == 2) {
long long ans = 0;
for (int i = P; i <= U; ++i) {
ans = gcd(ans, s2[i].query(1, input::C, s2[i].root, Q, V));
}
return ans;
} else {
assert(subtask == 3);
assert(P >= 1 && P <= input::R);
assert(U >= 1 && U <= input::R);
assert(P <= U);
assert(Q >= 1 && Q <= input::C);
assert(V >= 1 && V <= input::C);
assert(Q <= V);
return stree2d::query(1, input::R, 1, P, U, Q, V);
}
return 0LL;
}
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/cciQFaVv.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
