| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 898088 | Muhammad_Aneeq | Game (IOI13_game) | C++17 | 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 <numeric>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
int r,c;
int const N=1e5,N2=2000+10;;
// map<pair<int,int>,long long>d;
// struct seg1
// {
// long long St[4*N]={};
// void update(int i,int r,int st,int en,long long val)
// {
// if (st==en)
// {
// St[i]=val;
// return;
// }
// int mid=(st+en)/2;
// if (r<=mid)
// update(i*2,r,st,mid,val);
// else
// update(i*2+1,r,mid+1,en,val);
// St[i]=gcd(St[i*2],St[i*2+1]);
// }
// long long get(int i,int st,int en,int l,int r)
// {
// if (st>=l&&en<=r)
// return St[i];
// if (st>r||en<l)
// return 0;
// int mid=(st+en)/2;
// return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
// }
// };
struct seg2
{
long long St[2*N2]={};
void update(int i,int l,int r,int st,int en,long long val)
{
if (st>r||en<l)
return;
if (st>=l&&en<=r)
{
St[i]=val;return;
}
int mid=(st+en)/2;
update(i*2,l,r,st,mid,val);update(i*2+1,l,r,mid+1,en,val);
St[i]=gcd(St[i*2],St[i*2+1]);
}
long long get(int i,int st,int en,int l,int r)
{
if (st>=l&&en<=r)
return St[i];
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
};
// seg1 St[50]={};
seg2 St1[2*N2]={};
void update(int i,int l,int r,int k,int j,int st,int en,long long val)
{
if (st>r||en<l)
return ;
if (st>=l&&en<=r)
{
St1[i].update(1,k,k,0,c-1,val);
return;
}
int mid=(st+en)/2;
update(i*2,l,r,k,j,st,mid,val);update(i*2+1,l,r,k,j,mid+1,en,val);
long long f=gcd(St1[i*2].get(1,0,c-1,k,k),St1[i*2+1].get(1,0,c-1,k,k));
St1[i].update(1,k,k,0,c-1,f);
}
long long get(int i,int l,int r,int k,int j,int st,int en)
{
if (st>=l&&en<=r)
return St1[i].get(1,0,c-1,k,j);
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return gcd(get(i*2,l,r,k,j,st,mid),get(i*2+1,l,r,k,j,mid+1,en));
}
void init(int R, int C)
{
r=R;
c=C;
}
void update(int P, int Q, long long K)
{
// if (r<=10)
// St[P].update(1,Q,0,c-1,K);
// else
update(1,P,P,Q,Q,0,r-1,K);
}
long long calculate(int P, int Q, int U, int V)
{
// if (r<=10)
// {
// long long ans=0;
// for (int i=P;i<=U;i++)
// {
// long long z=St[i].get(1,0,c-1,Q,V);
// ans=gcd(ans,z);
// }
// return ans;
// }
long long ans=get(1,P,U,Q,V,0,r-1);
return ans;
}