#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int n;
struct NodeY{
int s,e,m;
ll v;
NodeY *l = NULL;
NodeY *r = NULL;
NodeY(int _s, int _e){
s=_s;e=_e;
m=(s+e)/2;
v=0;
if (s!=e){
l=new NodeY(s,m);
r=new NodeY(m+1,e);
}
}
void makeL(){
if (l!=NULL){
return;
}
l = new NodeY(s,m);
}
void makeR(){
if (r!=NULL){
return;
}
r = new NodeY(m+1,e);
}
ll getL(){
if (l==NULL){
return 0;
}
return l->v;
}
ll getR(){
if (r==NULL){
return 0;
}
return r->v;
}
void update(int ind, ll val){
//cout<<"y "<<s<<' '<<e<<'\n';
//cout<<"u "<<ind<<' '<<val<<'\n';
if (s==e){
v=val;
return;
}
if (ind<=m){
makeL();
l->update(ind,val);
} else {
makeR();
r->update(ind,val);
}
v=gcd2(getL(),getR());
}
ll queryL(int ya, int yb){
if (l==NULL){
return 0;
}
return l->query(ya,yb);
}
ll queryR(int ya, int yb){
if (r==NULL){
return 0;
}
return r->query(ya,yb);
}
ll query(int ya, int yb){
if (s==ya&&e==yb){
return v;
}
if (yb<=m){
return queryL(ya,yb);
} else if (m<ya){
return queryR(ya,yb);
} else {
return gcd2(queryL(ya,m),queryR(m+1,yb));
}
}
};
struct NodeX{
int s,e,m;
NodeY *v;
NodeX *l = NULL;
NodeX *r = NULL;
NodeX(int _s, int _e){
s=_s;e=_e;
m=(s+e)/2;
v=new NodeY(0,n-1);
if (s!=e){
l=new NodeX(s,m);
r=new NodeX(m+1,e);
}
}
void makeL(){
if (l!=NULL){
return;
}
l = new NodeX(s,m);
}
void makeR(){
if (r!=NULL){
return;
}
r = new NodeX(m+1,e);
}
void update(int indx, int indy, ll val){
//cout<<"x "<<s<<' '<<e<<'\n';
//cout<<"u "<<indx<<' '<<indy<<' '<<val<<'\n';
if (s==e){
v->update(indy,val);
return;
}
if (indx<=m){
makeL();
l->update(indx,indy,val);
} else {
makeR();
r->update(indx,indy,val);
}
v->update(indy,val); //???
}
ll queryL(int xa, int xb, int ya, int yb){
if (l==NULL){
return 0;
}
return l->query(xa,xb,ya,yb);
}
ll queryR(int xa, int xb, int ya, int yb){
if (r==NULL){
return 0;
}
return r->query(xa,xb,ya,yb);
}
ll query(int xa, int xb, int ya, int yb){
if (s==xa&&e==xb){
return v->query(ya,yb);
}
if (xb<=m){
return queryL(xa,xb,ya,yb);
} else if (m<xa){
return queryR(xa,xb,ya,yb);
} else {
return gcd2(queryL(xa,m,ya,yb),queryR(m+1,xb,ya,yb));
}
}
};
NodeX *root;
int x,y;
void init(int R, int C) {
/* ... */
x=R;y=C;
n=y;
root = new NodeX(0,x-1);
}
void update(int P, int Q, long long K) {
/* ... */
root->update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return root->query(P,U,Q,V);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2192 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
