#include "grader.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <tuple>
using namespace std;
const int N = 1e9;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct node
{
node *l, *r, *down;
long long val;
node() : l(0), r(0), down(0), val(0ll)
{
}
};
node *root;
long long get_val(node *t)
{
return t ? t->val : 0ll;
}
node *get_node()
{
static node T[7500 * 1000];
static int counter = 0;
return &T[counter++];
}
long long get_y(int yl,int yr, node *&t, int nl=0, int nr=N){
//printf("get_y %d %d %d %d %d %d\n", yl, yr, t, nl, nr,get_val(t));
if (!t)return 0ll;
if (yl <= nl && nr <= yr ){
return t->val;
}
else{
int m = (nl + nr) / 2;
long long cur = 0;
if (yl <= m)cur = gcd2(cur, get_y(yl, yr, t->l, nl, m));
if (yr > m)cur = gcd2(cur, get_y(yl, yr, t->r, m + 1, nr));
return cur;
}
}
long long get_x(int xl,int xr,int yl,int yr, node *&t, int nl=0, int nr=N){
//printf("get_x %d %d %d %d %d %d %d\n", xl, xr, yl, yr, t, nl, nr);
if (!t)return 0ll;
if (xl <= nl&&nr <= xr){
return get_y(yl, yr, t->down);
}
int m = (nl + nr) / 2;
long long cur = 0;
if (xl <= m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->l, nl, m));
if (xr > m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->r, m + 1, nr));
return cur;
}
void update_y(int y, long long val, node *&t, int nl=0, int nr=N){
//printf("update_y %d %lld %d %d %d\n", y, val, t, nl, nr);
if (!t)t = get_node();
if (nl == nr){
t->val = val; return;
}
int m = (nl + nr) / 2;
if (y <= m)update_y(y, val, t->l, nl, m);
else update_y(y, val, t->r, m + 1, nr);
t->val = gcd2( get_val(t->r), get_val(t->l));
}
void update_x(int x, int y, long long val, node *&t, int nl=0, int nr=N)
{
//printf("update_x %d %d %lld %d %d %d\n", x,y, val, t, nl, nr);
if (!t) t = get_node();
if (nl == nr){
update_y(y, val, t->down);
}
else{
int m = (nl + nr) / 2;
if (x <= m)update_x(x, y, val, t->l, nl, m);
else update_x(x, y, val, t->r, m + 1, nr);
update_y(y, gcd2(get_x(nl, m, y, y, t->l, nl, m), get_x(m + 1, nr, y, y, t->r, m + 1, nr)), t->down);
}
}
void init(int R, int C) {
}
void update(int P, int Q, long long K) { /* ... */
update_x(P, Q, K, root);
}
long long calculate(int P, int Q, int U, int V) {
long long ans = 0;
ans = get_x(P, U, Q, V, root);
return ans;
}
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;
^
game.cpp:1:20: fatal error: grader.h: No such file or directory
#include "grader.h"
^
compilation terminated.
