| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 499838 | aymanrs | 게임 (IOI13_game) | C++14 | 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 <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
if(a == 0 && b == 0) return 0;
return __gcd(a, b);
}
template<typename T>
struct node {
T v;
int l, r;
node<T> *left = nullptr, *right = nullptr;
node(){
l = 0;
r = 1e9-1;
}
node(int L, int R){
l = L;
r = R;
}
};
struct st {
node<long long> root;
st(){
root.v = 0;
}
void upd(node<long long>* i, int ind, long long v){
if(ind < i->l || ind > i->r) return;
if(i->l == i->r) {
i->v = v;
return;
}
int mid = (i->l+i->r)/2;
if(ind <= mid){
if(!i->left) {
i->left = new node<long long>(i->l, mid);
i->left->v = 0;
}
upd(i->left, ind, v);
} else {
if(!i->right){
i->right = new node<long long>(mid+1, i->r);
i->right->v = 0;
}
upd(i->right, ind, v);
}
i->v = gcd(i->left ? i->left->v : 0, i->right ? i->right->v : 0);
}
long long query(node<long long>* i, int a, int b){
if(b < i->l || i->r < a) return 0;
if(a <= i->l && i->r <= b) return i->v;
return gcd(i->left ? query(i->left, a, b) : 0, i->right ? query(i->right, a, b) : 0);
}
};
node<st> root;
long long query(node<st>* i, int a, int b, int x, int y){
if(b < i->l || i->r < a) return 0;
if(a <= i->l && i->r <= b) return i->v.query(&i->v.root, x, y);
return gcd(i->left ? query(i->left, a, b, x, y) : 0, i->right ? query(i->right, a, b, x, y) : 0);
}
void upd(node<st>* i, int x, int y, long long v){
if(x < i->l || i->r < x) return;
if(i->l == i->r){
i->v.upd(&i->v.root, y, v);
return;
}
int mid = (i->l+i->r) / 2;
if(x <= mid){
if(!i->left) i->left = new node<st>(i->l, mid);
upd(i->left, x, y, v);
int l = 0, r = 1e9-1;
node<long long> *root = &i->v.root, *a = &i->left->v.root, *b = i->right ? &i->right->v.root : 0;
while(true){
root->v = gcd(a->v, b?b->v:0);
if(l == r) return;
mid = (l+r)/2;
if(y <= mid){
if(!root->left) root->left = new node<long long>(l, mid);
r = mid;
root = root->left;
a = a->left;
if(b) b = b->left;
} else {
if(!root->right) root->right = new node<long long>(mid+1, r);
l = mid+1;
root = root->right;
a = a->right;
if(b) b = b->right;
}
}
} else {
if(!i->right) i->right = new node<st>(mid+1, i->r);
upd(i->right, x, y, v);
int l = 0, r = 1e9-1;
node<long long> *root = &i->v.root, *a = &i->right->v.root, *b = i->left ? &i->left->v.root : 0;
while(true){
root->v = gcd(a->v, b?b->v:0);
if(l == r) return;
mid = (l+r)/2;
if(y <= mid){
if(!root->left) root->left = new node<long long>(l, mid);
r = mid;
root = root->left;
a = a->left;
if(b) b = b->left;
} else {
if(!root->right) root->right = new node<long long>(mid+1, r);
l = mid+1;
root = root->right;
a = a->right;
if(b) b = b->right;
}
}
}
}
void init(int r, int c){
}
void update(int p, int q, long long k){
upd(&root, p, q, k);
}
long long calculate(int p, int q, int u, int v){
return query(&root, p, u, q, v);
}
// int main(){
// init(2, 3);
// update(0, 0, 20);
// update(0, 2, 15);
// update(1, 1, 12);
// cout << calculate(0, 0, 0, 2) << '\n';
// cout << calculate(0, 0, 1, 1) << '\n';
// update(0, 1, 6);
// update(1, 1, 14);
// cout << calculate(0, 0, 0, 2) << '\n';
// cout << calculate(0, 0, 1, 1) << '\n';
// }