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>
using namespace std;
int n,m,nn=0;
long long ga[12540069];
int pa[12540069][2];
long long gcd2(long long x,long long y)
{
for(;y;)
{
x%=y;
swap(x,y);
}
return x;
}
void sgud(int ix,int l,int r,int x,long long w)
{
if(l>=x&&r<=x)
{
ga[ix]=w;
}
else
{
int ii,md=(l+r)/2,l2,r2;
for(ii=0;ii<2;ii++)
{
l2=!ii?l:md+1;
r2=!ii?md:r;
if(!(l2>x||r2<x))
{
if(!pa[ix][ii])
{
nn++;
pa[ix][ii]=nn;
}
sgud(pa[ix][ii],l2,r2,x,w);
}
}
ga[ix]=gcd2(ga[pa[ix][0]],ga[pa[ix][1]]);
}
}
long long sgqr(int ix,int l,int r,int lh,int rh)
{
if(!ix||l>rh||r<lh)
{
return 0;
}
else if(l>=lh&&r<=rh)
{
return ga[ix];
}
else
{
long long md=(l+r)/2;
return gcd2(sgqr(pa[ix][0],l,md,lh,rh),sgqr(pa[ix][1],md+1,r,lh,rh));
}
}
struct segtreetree
{
int l,r,sg;
segtreetree *p[3];
void bd(int lh,int rh)
{
l=lh;
r=rh;
nn++;
sg=nn;
p[0]=0;
}
void blc()
{
if(!p[0])
{
int ii,md=l+(r-l)/3,md2=r-(r-l+2)/3;
for(ii=0;ii<3;ii++)
{
p[ii]=new segtreetree;
}
p[0]->bd(l,md);
p[1]->bd(md+1,md2);
p[2]->bd(md2+1,r);
}
}
long long ud(int y,int x,long long w)
{
if(l>y||r<y)
{
return sgqr(sg,0,m-1,x,x);
}
else if(!(l>=y&&r<=y))
{
int ii;
long long k=0;
blc();
for(ii=0;ii<3;ii++)
{
k=gcd2(k,p[ii]->ud(y,x,w));
}
w=k;
}
sgud(sg,0,m-1,x,w);
return w;
}
long long qr(int lh,int rh,int lh2,int rh2)
{
if(l>rh||r<lh)
{
return 0;
}
else if((l>=lh&&r<=rh)||!p[0])
{
return sgqr(sg,0,m-1,lh2,rh2);
}
else
{
long long ii,z=0;
for(ii=0;ii<3;ii++)
{
z=gcd2(z,p[ii]->qr(lh,rh,lh2,rh2));
}
return z;
}
}
}
sgg;
void init(int on,int om)
{
n=on;
m=om;
sgg.bd(0,n-1);
}
void update(int y,int x,long long w)
{
sgg.ud(y,x,w);
}
long long calculate(int y,int x,int y2,int x2)
{
return sgg.qr(y,y2,x,x2);
}
# | 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... |