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<vector>
#include<iostream>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<30;
ll gcd2(ll X,ll Y){
ll tmp;
while (X!=Y&&Y!=0){
tmp=X;
X=Y;
Y=tmp%Y;
}
return X;
}
// ===============================================================
// ===============================================================
// ===============================================================
struct Tree1{
ll val;
int ch1,ch2;
Tree1():val(0),ch1(-1),ch2(-1){}
};
int num1;
Tree1 trees1[9000000];
ll tree1_get_val(int node){
if(node==-1)
return 0;
return trees1[node].val;
}
int tree1_set(int node,int rl,int rr,int x,ll v){
if(node==-1)
node=num1++;
if(rl==rr-1){
trees1[node].val=v;
return node;
}
int mid=(rl+rr)/2;
if(x<mid){
trees1[node].ch1=tree1_set(trees1[node].ch1,rl,mid,x,v);
}else{
trees1[node].ch2=tree1_set(trees1[node].ch2,mid,rr,x,v);
}
trees1[node].val=gcd2(tree1_get_val(trees1[node].ch1),tree1_get_val(trees1[node].ch2));
return node;
}
ll tree1_get(int node,int rl,int rr,int x1,int x2){
if(node==-1)
return 0;
if(x2<=rl||rr<=x1)
return 0;
if(x1<=rl&&rr<=x2)
return trees1[node].val;
int mid=(rl+rr)/2;
return gcd2(tree1_get(trees1[node].ch1,rl,mid,x1,x2),tree1_get(trees1[node].ch2,mid,rr,x1,x2));
}
// ===============================================================
// ===============================================================
// ===============================================================
struct Tree2{
int val;
int ch1,ch2;
Tree2():ch1(-1),ch2(-1),val(-1){}
};
int num2;
Tree2 trees2[1000000];
ll tree2_get_val(int node,int x1,int x2){
if(node==-1)
return 0;
return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
}
int tree2_set(int node,int rl,int rr,int x,int y,ll v){
if(node==-1)
node=num2++;
if(rl==rr-1){
trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,v);
return node;
}
int mid=(rl+rr)/2;
if(y<mid){
trees2[node].ch1=tree2_set(trees2[node].ch1,rl,mid,x,y,v);
}else{
trees2[node].ch2=tree2_set(trees2[node].ch2,mid,rr,x,y,v);
}
ll val=gcd2(tree2_get_val(trees2[node].ch1,x,x+1),tree2_get_val(trees2[node].ch2,x,x+1));
trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,val);
return node;
}
ll tree2_get(int node,int rl,int rr,int x1,int x2,int y1,int y2){
if(node==-1)
return 0;
if(y2<=rl||rr<=y1)
return 0;
if(y1<=rl&&rr<=y2)
return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
int mid=(rl+rr)/2;
return gcd2(tree2_get(trees2[node].ch1,rl,mid,x1,x2,y1,y2),tree2_get(trees2[node].ch2,mid,rr,x1,x2,y1,y2));
}
// ===============================================================
// ===============================================================
// ===============================================================
void init(int h,int w){
num2=1;
}
void update(int y,int x,ll v){
tree2_set(0,0,TREE_SIZE,x,y,v);
}
ll calculate(int y1,int x1,int y2,int x2){
return tree2_get(0,0,TREE_SIZE,x1,x2+1,y1,y2+1);
}
Compilation message (stderr)
game.cpp: In constructor 'Tree2::Tree2()':
game.cpp:74:13: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
74 | int ch1,ch2;
| ^~~
game.cpp:73:9: warning: 'int Tree2::val' [-Wreorder]
73 | int val;
| ^~~
game.cpp:75:5: warning: when initialized here [-Wreorder]
75 | Tree2():ch1(-1),ch2(-1),val(-1){}
| ^~~~~
# | 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... |