#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct node{
node *ll=nullptr;
node *lr=nullptr;
node *rl=nullptr;
node *rr=nullptr;
node *tatko=nullptr;
long long value=0;
int id;
pair<long long,long long> x;
pair<long long,long long> y;
};
int p=0;
// trgni voa posle
long long gcd2(long long x,long long y)
{
if (x==0) return y;
if (y==0) return x;
if (x%y==0) return y;
return gcd2(y,x%y);
}
int stepen(int x)
{
int a = 1;
while(a<=x)
{
a*=2;
}
return a;
}
node koren;
void init(int R,int C)
{
int r = stepen(max(R,C));
koren.x.first =0;
koren.y.first =0;
koren.x.second=r-1;
koren.y.second=r-1;
koren.id = p;
p++;
}
void update1(long long r=0,long long c=0,long long v=0,node &n=koren)
{
//cout<< "ulava u "<<n.x.first<<" "<<n.x.second<< " "<<n.y.first<<" "<<n.y.second<<endl;
//system("pause");
if (n.x.first==n.x.second && n.y.first==n.y.second)
{
n.value = v;
return;
}
long long midx = (n.x.second+n.x.first)/2;
long long midy = (n.y.second+n.y.first)/2;
if (n.x.first<=r && r<=midx)
{
if (n.y.first<=c && c<=midy)
{
if (n.ll==nullptr)
{
node *nov = new node;
n.ll = nov;
nov->x={n.x.first,midx};
nov->y={n.y.first,midy};
nov->tatko=&n;
nov->value = v;
nov->id = p;
p++;
}
update1(r,c,v,*n.ll);
//n.ll->value = gcd2(n.ll->value,v);
}
if (n.y.second>=c && c>midy)
{
if (n.lr==nullptr)
{
node *nov = new node;
n.lr=nov;
nov->x={n.x.first,midx};
nov->y={midy+1,n.y.second};
nov->tatko=&n;
nov->value = v;
nov->id = p;
p++;
}
update1(r,c,v,*n.lr);
n.lr->value = gcd2(n.lr->value,v);
}
}
if (n.x.second>=r && r>midx)
{
if (c>=n.y.first && c<=midy)
{
if (n.rl==nullptr)
{
node *nov = new node;
n.rl=nov;
nov->x={midx+1,n.x.second};
nov->y={n.y.first,midy};
nov->tatko=&n;
nov->value = v;
nov->id = p;
p++;
}
update1(r,c,v,*n.rl);
//n.rl->value = gcd2(n.rl->value,v);
}
if (c<=n.y.second && c>midy)
{
if (n.rr==nullptr)
{
node *nov = new node;
n.rr=nov;
nov->x={midx+1,n.x.second};
nov->y={midy+1,n.y.second};
nov->tatko=&n;
nov->value = v;
nov->id = p;
p++;
}
update1(r,c,v,*n.rr);
//n.rr->value = gcd2(n.rr->value,v);
}
}
n.value = gcd2(n.value,v);
}
long long calculate1(long long lx=0,long long ty=0,long long rx=0,long long by=0,node &n=koren)
{
if (lx>n.x.second || ty>n.y.second || rx<n.x.first || by<n.y.first) return 0;
if (lx<=n.x.first && n.x.second<=rx && ty<=n.y.first && n.y.second<=n.y.second) return n.value;
long long odg=0;
if (n.ll) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.ll));
if (n.rl) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.rl));
if (n.lr) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.lr));
if (n.rr) odg = gcd2(odg,calculate1(lx,ty,rx,by,*n.rr));
return odg;
}
void update(int P, int Q,long long K)
{
update1(P,Q,K);
}
long long calculate(int P, int Q, int U, int V)
{
return calculate1(P,Q,U,V);
}
/*
int main()
{
/*
init(2,3);
update(0,0,20);
update(0,2,15);
update(1,1,12);
cout<<calculate(0,0,0,2)<<endl;
cout<<calculate(0,0,1,1)<<endl;
update(0,1,6);
update(1,1,14);
cout<<calculate(0,0,0,2)<<endl;
cout<<calculate(0,0,1,1)<<endl;
init(4,4);
update(0,0,10);
update(0,1,12);
update(0,2,14);
update(0,3,16);
update(1,0,20);
update(1,1,18);
update(1,3,100);
update(2,0,15);
update(2,2,0);
update(3,0,13);
update(3,1,13);
for (int x1=0;x1<4;x1++)
for (int x2=x1;x2<4;x2++)
for (int y1=0;y1<4;y1++)
for (int y2=y1;y2<4;y2++){
cout<< "od ("<<x1<<","<<y1<<") do ("<<x2<<","<<y2<<") = ";
cout<<calculate(x1,y1,x2,y2)<<endl;
}
cout<<"0,0 -> 1,1 = "<<calculate(0,0,1,1)<<endl;
cout<<"0,2 -> 1,3 = "<<calculate(0,2,1,3)<<endl;
cout<<"0,0 -> 2,0 = "<<calculate(0,0,2,0)<<endl;
cout<<"2,2 -> 3,3 = "<<calculate(2,2,3,3)<<endl;
cout<<"3,0 -> 3,1 = "<<calculate(3,0,3,1)<<endl;
cout<<"2,0 -> 2,0 = "<<calculate(2,0,2,0)<<endl;
cout<<"1,1 -> 2,2 = "<<calculate(1,1,2,2)<<endl;
return 0;
}
*/
Compilation message
game.cpp:162:1: warning: "/*" within comment [-Wcomment]
162 | /*
|
game.cpp: In function 'long long int calculate1(long long int, long long int, long long int, long long int, node&)':
game.cpp:140:71: warning: self-comparison always evaluates to true [-Wtautological-compare]
140 | if (lx<=n.x.first && n.x.second<=rx && ty<=n.y.first && n.y.second<=n.y.second) return n.value;
| ~~~~~~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
