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;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
long long pot (long long x){
long long tmp = 1;
while(x){
x/=2;
tmp*=2;
}
return tmp;
}
long long treeSizeX, treeSizeY;
struct node{
node *right = nullptr, *left = nullptr;
long long val = 0;
};
struct tree{
tree *left = nullptr, *right = nullptr;
node *root = nullptr;
};
void malyUpdate(long long v, long long a, node *rt, long long q = 0, long long r = treeSizeX-1){
//cout<<q<<" "<<r<<" "<<rt->val<<endl;
if(q==r){
rt->val = v;
return;
}
long long mid = (q+r)/2;
if(a<=mid){
if(rt->left==nullptr) rt->left = new node();
malyUpdate(v, a, rt->left, q, mid);
rt->val = rt->left->val;
if(rt->right!=nullptr) rt->val = gcd2(rt->val, rt->right->val);
}
if(a>mid){
if(rt->right==nullptr) rt->right = new node();
malyUpdate(v, a,rt->right, mid+1, r);
rt->val = rt->right->val;
if(rt->left!=nullptr) rt->val = gcd2(rt->val, rt->left->val);
}
}
void sredniUpdate(long long a, node *rt1, node *rt2, node *rt4, long long q = 0, long long r = treeSizeX-1){
if(q==r){
rt4->val = gcd2(rt1->val, rt2==nullptr?0:rt2->val);
return;
}
long long mid = (q+r)/2;
if(a<=mid){
if(rt4->left==nullptr) rt4->left = new node();
sredniUpdate(a, rt1->left, rt2==nullptr?nullptr:rt2->left, rt4->left, q, mid);
}
if(a>mid){
if(rt4->right==nullptr) rt4->right = new node();
sredniUpdate(a, rt1->right, rt2==nullptr?nullptr:rt2->right, rt4->right, mid+1, r);
}
rt4->val = rt1->val;
if(rt2!=nullptr) rt4->val = gcd2(rt1->val, rt2->val);
}
tree *drzewo;
void duzyUpdate(long long v, long long x, long long y, long long q = 0, long long r = treeSizeY-1, tree *rt = drzewo){
if(rt->root==nullptr) rt->root = new node();
if(q==r){
malyUpdate(v, x, rt->root);
return;
}
long long mid = (q+r)/2;
if(y<=mid){
if(rt->left==nullptr) rt->left = new tree();
duzyUpdate(v, x, y, q, mid, rt->left);
sredniUpdate(x, rt->left->root, rt->right==nullptr?nullptr:rt->right->root, rt->root);
}else{
if(rt->right==nullptr) rt->right = new tree();
duzyUpdate(v, x, y, mid+1, r, rt->right);
sredniUpdate(x, rt->right->root, rt->left==nullptr?nullptr:rt->left->root, rt->root);
}
}
long long malyQur(long long a, long long b, node *rt, long long q = 0, long long r = treeSizeX-1){
//cout<<q<<" "<<r<<" "<<rt->val<<endl;
if(a==q&&b==r){
return rt->val;
}
long long mid = (q+r)/2;
long long out = 0;
if(a<=mid){
if(rt->left!=nullptr){
out = malyQur(a, min(b, mid), rt->left, q, mid);
}
}
if(b>mid){
if(rt->right!=nullptr){
out = gcd2(out, malyQur(max(a, mid+1), b, rt->right, mid+1, r));
}
}
return out;
}
long long duzyQur(long long x1, long long x2, long long y1, long long y2, tree *rt, long long q = 0, long long r = treeSizeY-1){
//cout<<q<<" "<<r<<" "<<y1<<"-"<<y2<<endl;
if(y1==q&&y2==r){
return malyQur(x1, x2, rt->root);
}
long long out = 0;
long long mid = (q+r)/2;
if(y1<=mid){
if(rt->left!=nullptr){
out = duzyQur(x1, x2, y1, min(y2, mid), rt->left, q, mid);
}
}
if(y2>mid){
if(rt->right!=nullptr){
out = gcd2(out, duzyQur(x1, x2, max(y1, mid+1), y2, rt->right, mid+1, r));
}
}
return out;
}
void init(int R, int C) {
swap(R, C);
treeSizeY = pot(R);
treeSizeX = pot(C);
drzewo = new tree();
}
void update(int P, int Q, long long K) {
duzyUpdate(K, P, Q);
}
long long calculate(int P, int Q, int U, int V) {
return duzyQur(P, U, Q, V, drzewo);
}
# | 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... |