#pragma once
#include <bits/stdc++.h>
using namespace std;
const int SZ = 1e9+1;
const int SMALL_SZ = 1.5e7;
struct smallnode {
long long ans;
int left, right;
smallnode() {
ans = 0, left = -1, right = -1;
}
};
vector<smallnode> smalls;
int nxt_free = 0;
int create() {
smalls.push_back(smallnode());
return nxt_free++;
}
struct bignode {
int left, right;
int root;
bignode() {
root = -1, left = -1, right = -1;
}
void update(int idx, long long val, int x = 0, int tl = 0, int tr = SZ) {
if (tl == tr) {
smalls[x].ans = val;
return;
}
int m = (tl + tr) >> 1;
if (idx <= m) {
if (smalls[x].left == -1) {
smalls[x].left = create();
}
update(idx, val, smalls[x].left, tl, m);
}
else {
if (smalls[x].right == -1) {
smalls[x].right = create();
}
update(idx, val, smalls[x].right, m+1, tr);
}
smalls[x].ans = (smalls[x].left == -1 ? 0 : smalls[smalls[x].left].ans);
smalls[x].ans = __gcd(smalls[x].ans, (smalls[x].right == -1 ? 0 : smalls[smalls[x].right].ans));
}
long long query(int l, int r, int x = 0, int tl = 0, int tr = SZ) {
if (tl >= l && tr <= r) return smalls[x].ans;
if (tr < l || tl > r) return 0;
int m = (tl + tr) >> 1;
long long from_r = (smalls[x].right == -1 ? 0 : query(l, r, smalls[x].right, m+1, tr));
long long from_l = (smalls[x].left == -1 ? 0 : query(l, r, smalls[x].left, tl, m));
return __gcd(from_l, from_r);
}
};
vector<bignode> bigs;
int nxt_free_big = 0;
int create_big() {
bigs.push_back(bignode());
bigs[nxt_free_big].root = create();
return nxt_free_big++;
}
struct segtree {
void update(int i, int j, long long val, int x = 0, int tl = 0, int tr = SZ) {
if (tl == tr) {
bigs[x].update(j, val, bigs[x].root);
return;
}
int m = (tl + tr) >> 1;
if (i <= m) {
if (bigs[x].left == -1) {
bigs[x].left = create_big();
}
update(i, j, val, bigs[x].left, tl, m);
}
else {
if (bigs[x].right == -1) {
bigs[x].right = create_big();
}
update(i, j, val, bigs[x].right, m+1, tr);
}
long long from_l = (bigs[x].left == -1 ? 0 : bigs[bigs[x].left].query(j, j, bigs[bigs[x].left].root));
long long from_r = (bigs[x].right == -1 ? 0 : bigs[bigs[x].right].query(j, j, bigs[bigs[x].right].root));
bigs[x].update(j, __gcd(from_l, from_r), bigs[x].root);
}
long long query(int l, int r, int jl, int jr, int x = 0, int tl = 0, int tr = SZ) {
if (tl >= l && tr <= r) {
return bigs[x].query(jl, jr, bigs[x].root);
}
if (tl > r || l > tr) return 0;
int m = (tl + tr) >> 1;
long long from_l = 0;
long long from_r = 0;
if (bigs[x].left != -1) from_l = query(l, r, jl, jr, bigs[x].left, tl, m);
if (bigs[x].right != -1) from_r = query(l, r, jl, jr, bigs[x].right, m+1, tr);
return __gcd(from_l, from_r);
}
};
const int SQ = 1e3+1;
segtree now;
void init(int R, int C) {
create_big();
}
void update(int P, int Q, long long K) {
now.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
// cerr << smalls.size() << " " << bigs.size() << endl;
return now.query(P, U, Q, V);
}
Compilation message
game.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
/usr/bin/ld: /tmp/cc8N7Dsb.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status
