// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 22005, SQ = 800;
int n, X[N], Y[N], P[N], rev[N];
ll Z[N];
vector < int > UX, UY, V[N];
map < pair < int , int > , int > MP;
struct Tree
{
int m;
vector < ll > G;
vector < int > A;
inline void Build()
{
m = (int)A.size();
G.resize(m + m);
for (int i = 0; i < m; i ++)
G[i + m] = Z[A[i]];
for (int i = m - 1; i; i --)
G[i] = __gcd(G[i << 1], G[i << 1 ^ 1]);
}
inline void Set(int i)
{
printf("%d :: %d\n", m, (int)A.size());
G[i + m] = Z[A[i]];
for (i += m; i > 1; i >>= 1)
G[i >> 1] = __gcd(G[i], G[i ^ 1]);
}
inline ll Get(int l, int r)
{
ll g = 0;
for (l += m, r += m; l < r; l >>= 1, r >>= 1)
{
if (l & 1) g = __gcd(g, G[l ++]);
if (r & 1) g = __gcd(g, G[-- r]);
}
return (g);
}
};
Tree S[N * 2];
inline bool CMPY(int i, int j)
{
return (Y[i] < Y[j]);
}
inline void Build()
{
int m = (int)UX.size();
for (int i = m; i < m + m; i ++)
S[i].A = vector < int > {rev[i - m]}, S[i].Build();
for (int i = m - 1; i; i --)
{
int lc = i << 1, rc = lc ^ 1;
S[i].A.clear();
merge(S[lc].A.begin(), S[lc].A.end(), S[rc].A.begin(), S[rc].A.end(), back_inserter(S[i].A), CMPY);
S[i].Build();
}
for (int i = 0; i < n; i ++)
V[i].clear();
for (int i = m + m - 1; i; i --)
for (int j = 0; j < S[i].m; j ++)
V[S[i].A[j]].push_back(j);
}
inline void Set(int i)
{
int id = rev[i], ptr = 0;
for (i += (int)UX.size(); i; i >>= 1)
S[i].Set(V[id][ptr]), ptr ++;
}
inline ll Get(int l, int r, int le, int ri)
{
ll g = 0;
for (l += (int)UX.size(), r += (int)UX.size(); l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
int lb = lower_bound(S[l].A.begin(), S[l].A.end(), le, CMPY) - S[l].A.begin();
int ub = lower_bound(S[l].A.begin(), S[l].A.end(), ri, CMPY) - S[l].A.begin();
g = __gcd(g, S[l].Get(lb, ub));
l ++;
}
if (r & 1)
{
r --;
int lb = lower_bound(S[r].A.begin(), S[r].A.end(), le, CMPY) - S[r].A.begin();
int ub = lower_bound(S[r].A.begin(), S[r].A.end(), ri, CMPY) - S[r].A.begin();
g = __gcd(g, S[r].Get(lb, ub));
}
}
return (g);
}
inline void Init()
{
UX.clear();
UY.clear();
for (int i = 0; i < n; i ++)
UX.push_back(X[i]),
UY.push_back(Y[i]);
sort(UX.begin(), UX.end());
sort(UY.begin(), UY.end());
memset(rev, -1, sizeof(rev));
for (int i = 0; i < n; i ++)
{
int lb = lower_bound(UX.begin(), UX.end(), X[i]) - UX.begin();
while (~ rev[lb]) lb ++;
rev[lb] = i;
P[i] = lb;
}
Build();
}
void init(int _, int __)
{
}
void update(int a, int b, ll c)
{
if (MP.count({a, b}))
{
int i = MP[{a, b}];
Z[i] = c;
if (i < n / SQ * SQ)
Set(P[i]);
return ;
}
MP[{a, b}] = n;
X[n] = a; Y[n] = b; Z[n] = c; n ++;
if (n % SQ == 0)
Init();
}
ll calculate(int a, int b, int c, int d)
{
if (a > c) swap(a, c);
if (b > d) swap(b, d);
c ++; d ++;
int aa = lower_bound(UX.begin(), UX.end(), a) - UX.begin();
int cc = lower_bound(UX.begin(), UX.end(), c) - UX.begin();
Y[n + 1] = b; Y[n + 2] = d;
ll g = Get(aa, cc, n + 1, n + 2);
for (int i = n / SQ * SQ; i < n; i ++)
if (a <= X[i] && X[i] < c && b <= Y[i] && Y[i] < d)
g = __gcd(g, Z[i]);
return (g);
}
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/ccRSoFkX.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
