이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
const ll MAXN = 2e3 + 10;
long long gcd2(long long X, long long Y) {
if(X == 0 && Y == 0)
return 0;
else if(X == 0 && Y != 0)
return Y;
else if(X != 0 && Y == 0)
return X;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll n,m;
/// 2D SEGMENT TREE CODE
struct segment_tree_2d
{
/// SEGMENT TREE CODE
struct segment_tree
{
/// NODE CODE
struct node
{
node *l;
node *r;
ll val;
node()
{
val = 0;
l = nullptr;
r = nullptr;
}
node(ll _val)
{
val = _val;
l = nullptr;
r = nullptr;
}
};
node *root;
segment_tree *l;
segment_tree *r;
segment_tree()
{
root = new node();
l = nullptr;
r = nullptr;
}
void merge_nodes(node *tree)
{
if(tree -> l == nullptr)
tree -> l = new node();
if(tree -> r == nullptr)
tree -> r = new node();
tree -> val = gcd2(tree -> l -> val, tree -> r -> val);
}
void update(node *tree, ll left, ll right, ll pos, ll x)
{
if(left == right)
{
tree -> val = x;
return;
}
ll mid = left + (right - left) / 2;
if(pos <= mid)
{
if(tree -> l == nullptr)
tree -> l = new node();
update(tree -> l, left, mid, pos, x);
}
else
{
if(tree -> r == nullptr)
tree -> r = new node();
update(tree -> r, mid + 1, right, pos, x);
}
merge_nodes(tree);
}
ll query(node *tree, ll left, ll right, ll qleft, ll qright)
{
if(tree == nullptr)
return 0LL;
if(qright < left || right < qleft)
return 0LL;
if(qleft <= left && right <= qright)
return tree -> val;
ll mid = left + (right - left) / 2;
ll Lnode = query(tree -> l, left, mid, qleft, qright);
ll Rnode = query(tree -> r, mid + 1, right, qleft, qright);
return gcd2(Lnode, Rnode);
}
void update(ll pos, ll x)
{
update(root, 0, m - 1, pos, x);
}
ll query(ll qleft, ll qright)
{
return query(root, 0, m - 1, qleft, qright);
}
};
segment_tree *root;
segment_tree_2d()
{
root = new segment_tree();
}
void merge(segment_tree *tree, ll pos)
{
if(tree -> l == nullptr)
tree -> l = new segment_tree();
if(tree -> r == nullptr)
tree -> r = new segment_tree();
ll Lnode = tree -> l -> query(pos, pos);
ll Rnode = tree -> r -> query(pos, pos);
tree -> update(pos, gcd2(Lnode, Rnode));
}
void update(segment_tree *tree, ll left, ll right, ll row, ll col, ll x)
{
if(left == right)
{
tree -> update(col, x);
return;
}
ll mid = left + (right - left) / 2;
if(row <= mid)
{
if(tree -> l == nullptr)
tree -> l = new segment_tree();
update(tree -> l, left, mid, row, col, x);
}
else
{
if(tree -> r == nullptr)
tree -> r = new segment_tree();
update(tree -> r, mid + 1, right, row, col, x);
}
merge(tree, col);
}
ll query(segment_tree *tree, ll left, ll right, ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
{
if(tree == nullptr)
return 0LL;
if(qright_row < left || right < qleft_row)
return 0LL;
if(qleft_row <= left && right <= qright_row)
return tree -> query(qleft_col, qright_col);
ll mid = left + (right - left) / 2;
ll Lnode = query(tree -> l, left, mid, qleft_row, qright_row, qleft_col, qright_col);
ll Rnode = query(tree -> r, mid + 1, right, qleft_row, qright_row, qleft_col, qright_col);
return gcd2(Lnode, Rnode);
}
void update(ll row, ll col, ll x)
{
update(root, 0, n - 1, row, col, x);
}
ll query(ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
{
return query(root, 0, n - 1, qleft_row, qright_row, qleft_col, qright_col);
}
};
segment_tree_2d s;
void init(int R, int C)
{
n = R;
m = C;
}
void update(int i, int j, long long k)
{
s.update(i,j,k);
}
ll calculate(int i1, int j1, int i2, int j2)
{
ll result = s.query(i1, i2, j1, j2);
return result;
}
/**
int main()
{
ll r,c,n;
cin >> r >> c >> n;
init(r,c);
for(int i = 0; i < n; i++)
{
ll type;
cin >> type;
if(type == 1)
{
ll x,y,w;
cin >> x >> y >> w;
update(x,y,w);
}
else
{
ll i1,j1,i2,j2;
cin >> i1 >> j1 >> i2 >> j2;
cout << calculate(i1, j1, i2, j2) << endl;
}
}
return 0;
}
*/
# | 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... |