#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define orset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#pragma GCC optimize("O3")
// #pragma GCC target("sse", "sse2", "sse3", "sse4")
//#pragma GCC target("avx2")
#define int long long
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
#define all(a) (a.begin()), (a.end())
#define gsz(x) ((int)x.size())
#define endl "\n"
#define LOCAL
#ifdef LOCAL
#define dbg(x) cerr << #x << ":" << (x) << endl
#define print(x) cerr << (x) << endl
#else
#define dbg(x) 0
#define print(x) 0
#endif
using namespace std;
using namespace __gnu_pbds;
const int N = 2e6 + 10;
const int B = 340;
const ll inf = 1e18 + 10;
const ll mod = 1e9 + 7;
mt19937 rnd(4);//chrono::high_resolution_clock::now().time_since_epoch().count());
long long gcd2(long long X, long long Y) {
assert(X >= 0 && Y >= 0);
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct nodey{
int y, prior = rnd();
int val, gcd;
int l = -1, r = -1;
};
struct nodex{
int l = -1, r = -1;
int rooty = -1;
};
nodex tx[N];
nodey ty[N];
int n, m;
int topx = 0, topy = 0;
int rootx = -1;
int getgcd(int v)
{
return v == -1 ? 0 : ty[v].gcd;
}
void updy(int v)
{
if(v == -1) return;
ty[v].gcd = gcd2(gcd2(ty[v].val, getgcd(ty[v].l)), getgcd(ty[v].r));
}
int mergey(int l, int r)
{
if(l == -1) return r;
if(r == -1) return l;
if(ty[l].prior > ty[r].prior)
{
ty[l].r = mergey(ty[l].r, r);
updy(l);
return l;
}
else
{
ty[r].l = mergey(l, ty[r].l);
updy(r);
return r;
}
}
pii splity(int v, int k)
{
if(v == -1) return {-1, -1};
if(ty[v].y > k)
{
pii p = splity(ty[v].l, k);
ty[v].l = p.y;
updy(v);
return {p.x, v};
}
else
{
pii p = splity(ty[v].r, k);
ty[v].r = p.x;
updy(v);
return {v, p.y};
}
}
int createx()
{
int v = topx++;
return v;
}
int gety(int &v, int ly, int ry)
{
pii p1 = splity(v, ly - 1);
pii p2 = splity(p1.y, ry);
int val = getgcd(p2.x);
v = mergey(p1.x, mergey(p2.x, p2.y));
return val;
}
int getx(int tl, int tr, int v, int lx, int rx, int ly, int ry)
{
if(v == -1)
return 0;
if(tl > rx || tr < lx)
return 0;
if(tl >= lx && tr <= rx)
return gety(tx[v].rooty, ly, ry);
int mid = (tl + tr) / 2;
return gcd2(getx(tl, mid, tx[v].l, lx, rx, ly, ry), getx(mid + 1, tr, tx[v].r, lx, rx, ly, ry));
}
int createy(int y, int val)
{
int v = topy++;
ty[v].y = y;
ty[v].val = ty[v].gcd = val;
return v;
}
void changey(int &v, int y, int val)
{
pii p1 = splity(v, y - 1);
pii p2 = splity(p1.y, y);
v = mergey(p1.x, mergey(createy(y, val), p2.y));
}
int changex(int tl, int tr, int v, int x, int y, int val)
{
if(tl > x || tr < x)
return v;
if(v == -1)
v = createx();
changey(tx[v].rooty, y, val);
if(tl == tr)
return v;
int mid = (tl + tr) / 2;
tx[v].l = changex(tl, mid, tx[v].l, x, y, val);
tx[v].r = changex(mid + 1, tr, tx[v].r, x, y, val);
return v;
}
void init(int32_t n, int32_t m)
{
::n = n;
::m = m;
}
void update(int32_t x, int32_t y, ll val)
{
rootx = changex(0, 1e9, rootx, x, y, val);
}
long long calculate(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
{
return getx(0, 1e9, rootx, x1, x2, y1, y2);
}
Compilation message
Compilation timeout while compiling game
