This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "game.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
typedef long long ll;
const int Nmax = 2005;
int N, M, Nr100, Nr10, Y1, Y2;
ll ans, a[Nmax + 200][Nmax + 200];
ll gcd2(ll X, ll Y)
{
if(!Y) return X;
ll rest = X % Y;
while(rest)
X = Y, Y = rest, rest = X % Y;
return Y;
}
class SegTree
{
ll a[Nmax<<2];
public:
void update(int node, int st, int dr, int pos, ll val)
{
if(st == dr)
{
a[node] = val;
return;
}
if(pos <= mid) update(left_son, st, mid, pos, val);
else update(right_son, mid+1, dr, pos, val);
a[node] = gcd2(a[left_son], a[right_son]);
}
void query(int node, int st, int dr, int L, int R)
{
if(L <= st && dr <= R)
{
ans = gcd2(a[node], ans);
return;
}
if(L <= mid) query(left_son, st, mid, L, R);
if(mid < R) query(right_son, mid+1, dr, L, R);
}
} aint[2 * Nmax];
void init(int R, int C)
{
if(!(R <= 2000 && C <= 2000)) exit(0);
N = R; M = C;
Nr100 = (R-1) / 100 + 1;
Nr10 = (R-1) / 10 + 1;
}
int up(int x, int y) /// primul multiplu de y care e >= x
{
return (x + y - 1) / y;
}
int down(int x, int y)
{
if(x + 1 - y < 0) return -1;
return (x - y + 1) / y;
}
void update(int x, int y, ll K)
{
a[x][y] = K;
int i, id;
ll val;
id = x / 100; val = 0;
for(i = id*100; i < id*100 + 100; ++i) val = gcd2(a[i][y], val);
aint[id].update(1, 0, M-1, y, val);
id = x / 10; val = 0;
for(i = id*10; i < id*10 + 10; ++i) val = gcd2(a[i][y], val);
aint[id + Nr100].update(1, 0, M-1, y, val);
aint[x + Nr100 + Nr10].update(1, 0, M-1, y, K);
}
void query1(int l, int r)
{
if(l > r) return;
int i;
for(i=l; i<=r; ++i)
aint[Nr100 + Nr10 + i].query(1, 0, M-1, Y1, Y2);
}
void query10(int l, int r)
{
if(l > r) return;
int i, L = up(l, 10), R = down(r, 10);
if(L > R)
{
query1(l, r);
return;
}
for(i=L; i<=R; ++i)
aint[i + Nr100].query(1, 0, M-1, Y1, Y2);
query1(l, L * 10 - 1);
query1(R * 10 + 10, r);
}
void query100(int l, int r)
{
if(l > r) return;
int i, L = up(l, 100), R = down(r, 100);
if(L > R)
{
query10(l, r);
return;
}
for(i=L; i<=R; ++i)
aint[i].query(1, 0, M-1, Y1, Y2);
query10(l, L * 100 - 1);
query10(R * 100 + 100, r);
}
ll calculate(int P, int Q, int U, int V)
{
int X1, X2;
X1 = min(P, U);
X2 = max(P, U);
Y1 = min(Q, V);
Y2 = max(Q, V);
ans = 0;
query100(X1, X2);
return ans;
}
Compilation message (stderr)
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |