| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 581403 | ggoh | Game (IOI13_game) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
long long K;
struct X
{
X *left, *right;
Y *ynode;
X(){left=right=NULL;ynode=new Y();}
int s, e;
}*inix;
struct Y
{
Y *left, *right ;
Y(){left=right=NULL;val=0;}
long long val;
int s,e;
};
long long gcd2(long long xx, long long yy)
{
if (yy == 0)
return xx;
return gcd2(yy, xx % yy);
}
void yup(Y *y, int yco, long long v)
{
int s1 = y->s, e1 = y->e;
if (s1 == e1)
{
y->val = v;
return;
}
if ((s1 + e1) / 2 >= yco)
{
if (!y->left)
{
y->left=new Y();
y->left->s=s1;
y->left->e=(s1+e1)/2;
}
yup(y->left, yco, v);
}
else
{
if (!y->right)
{
y->right=new Y();
y->right->s=(s1+e1)/2+1;
y->right->e=e1;
}
yup(y->right, yco, v);
}
long long l = 0, r = 0;
if (y->left)
l = y->left->val;
if (y->right)
r = y->right->val;
y->val = gcd2(l, r);
}
void hardyup(Y *y, Y *ly, Y *ry, int yco)
{
int s1 = y->s, e1 = y->e;
Y *nextl=NULL, *nextr=NULL;
long long l = 0, r = 0;
if (ly)
{
l =ly->val;
}
if (ry)
{
r = ry->val;
}
y->val = gcd2(l, r);
if (s1 == e1)
return;
if (yco <= (s1 + e1) / 2)
{
if (ly)
nextl = ly->left;
if(ry)
nextr=ry->left;
if (!y->left)
{
y->left = new Y();
y->left->s=s1,
y->left->e=(s1 + e1) / 2;
}
hardyup(y->left, nextl, nextr, yco);
}
else
{
if (ly)
nextl = ly->right;
if(ry)
nextr=ry->right;
if (!y->right)
{
y->right = new Y();
y->right->s=(s1 + e1) / 2+1;
y->right->e=e1;
}
hardyup(y->right, nextl, nextr, yco);
}
}
void xup(X *x, int xco, int yco, long long v)
{
int s1 = x->s, e1 = x->e;
if (s1 == e1)
{
if(!x->ynode)x->ynode=new Y();
yup(x->ynode, yco, v);
return;
}
if ((s1 + e1) / 2 >= xco)
{
if (!x->left)
{
x->left = new X();
x->left->s=s1;
x->left->e=(s1 + e1) / 2;
x->left->ynode=new Y();
x->left->ynode->s=0;
x->left->ynode->e=C-1;
}
xup(x->left, xco, yco, v);
}
else
{
if (!x->right)
{
x->right = new X();
x->right->s=(s1 + e1) / 2 + 1;
x->right->e = e1;
x->right->ynode=new Y();
x->right->ynode->s=0;
x->right->ynode->e=C-1;
}
xup(x->right, xco, yco, v);
}
Y *ly=NULL,*ry=NULL;
if (x->left)
ly= x->left->ynode;
if (x->right)
ry=x->right->ynode;
hardyup(x->ynode, ly, ry, yco);
}
long long yans(Y *y, int py, int qy)
{
if (y->s > qy || y->e < py)
return 0ll;
if (py <= y->s && y->e <= qy)
return y->val;
long long l = 0, r = 0;
if (y->left)
l = yans(y->left, py, qy);
if (y->right)
r = yans(y->right, py, qy);
return gcd2(l, r);
}
long long xans(X *x, int px, int qx, int py, int qy)
{
if (x->s > qx || x->e < px)
return 0ll;
if (px <= x->s && x->e <= qx)
{
return yans(x->ynode, py, qy);
}
long long l = 0, r = 0;
if (x->left)
l = xans(x->left, px, qx, py, qy);
if (x->right)
r = xans(x->right, px, qx, py, qy);
return gcd2(l, r);
}
void init(int RR, int CC)
{
R=RR;
C=CC;
inix=new X();
inix->s=0;
inix->e=R-1;
inix->ynode=new Y();
inix->ynode->s=0;
inix->ynode->e=C-1;
}
void update(int P,int Q,long long K)
{
xup(inix, P, Q, K);
}
long long calculate(int P,int Q,int U,int V)
{
return xans(inix, P, U, Q, V);
}