#include <bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 random_generator(23799931);
long long gcd(long long a, long long b)
{
while (b)
{
long long r = a % b;
a = b;
b = r;
}
return a;
}
struct node
{
long long val, subtree_val;
int key, prior;
node *left, *right;
node() {}
node(int _key, long long _val) {key = _key, val = subtree_val = _val, prior = random_generator(), left = right = nullptr;}
};
long long subtree_val(node *x)
{
return x ? x->subtree_val : 0;
}
void recalc(node *&x)
{
if (!x)
return;
x->subtree_val = gcd(gcd(subtree_val(x->left), subtree_val(x->right)), x->val);
}
void merge(node *a, node *b, node *&ans)
{
if (!a || !b)
ans = a ? a : b;
else
if (a->prior > b->prior)
merge(a->right, b, a->right), ans = a;
else
merge(a, b->left, b->left), ans = b;
recalc(ans);
}
void split(node *x, int val, node *&l, node *&r)
{
if (!x)
l = r = nullptr;
else
if (x->key <= val)
{
split(x->right, val, x->right, r);
l = x;
recalc(l);
}
else
{
split(x->left, val, l, x->left);
r = x;
recalc(r);
}
}
void insert(node *&ans, node *x)
{
if (!ans)
ans = x;
else
if (x->prior > ans->prior)
{
split(ans, x->key, x->left, x->right);
ans = x;
recalc(ans);
}
else
if (x->key < ans->key)
insert(ans->left, x);
else
insert(ans->right, x);
recalc(ans);
}
void erase(node *&ans, int x)
{
if (!ans)
return;
if (ans->key == x)
merge(ans->left, ans->right, ans);
else
if (x < ans->key)
erase(ans->left, x);
else
erase(ans->right, x);
recalc(ans);
}
long long dfs(node *x, int l, int r)
{
if (!x)
return 0;
long long ans = gcd(dfs(x->left, l, r), dfs(x->right, l, r));
if (x->key >= l && x->key <= r)
ans = gcd(ans, x->val);
return ans;
}
long long get(node *x, int l, int r)
{
/*
pair <node*, node*> temp, temp1;
split(x, r, temp.first, temp.second);
split(temp.first, l-1, temp1.first, temp1.second);
long long ans = subtree_val(temp1.second);
merge(temp1.first, temp1.second, temp.first);
merge(temp.first, temp.second, x);
return ans;
*/
return dfs(x, l, r);
}
struct segment_tree
{
node *root;
segment_tree *left, *right;
set <pair <int, long long> > s;
segment_tree() {root = nullptr, left = right = nullptr;}
};
segment_tree *tr;
int r, c;
void init(int _r, int _c)
{
tr = new segment_tree();
r = _r;
c = _c;
}
void big_erase(segment_tree *&tr, int l, int r, int x, int y)
{
if (!tr)
return;
auto it = tr->s.lower_bound({y, 0});
if (it != tr->s.end() && it->first == y)
tr->s.erase(it);
erase(tr->root, y);
if (l == r)
return;
int mid = (l + r) / 2;
if (x <= mid)
big_erase(tr->left, l, mid, x, y);
else
big_erase(tr->right, mid + 1, r, x, y);
}
void big_insert(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
tr->s.insert({y, val});
insert(tr->root, new node(y, val));
if (l == r)
return;
int mid = (l + r) / 2;
if (x <= mid)
{
if (!tr->left)
tr->left = new segment_tree();
big_insert(tr->left, l, mid, x, y, val);
}
else
{
if (!tr->right)
tr->right = new segment_tree();
big_insert(tr->right, mid + 1, r, x, y, val);
}
}
long long big_get(segment_tree *&tr, int l, int r, int lx, int rx, int ly, int ry)
{
if (!tr || l > rx || r < lx)
return 0;
if (l >= lx && r <= rx)
{
long long val = 0;
for (auto i: tr->s)
if (i.first >= ly && i.first <= ry)
val = gcd(val, i.second);
//return get(tr->root, ly, ry);
return val;
}
int mid = (l + r) / 2;
return gcd(big_get(tr->left, l, mid, lx, rx, ly, ry), big_get(tr->right, mid + 1, r, lx, rx, ly, ry));
}
void update(int p, int q, long long k)
{
big_erase(tr, 0, r-1, p, q);
big_insert(tr, 0, r-1, p, q, k);
}
long long calculate(int p, int q, int u, int v)
{
return big_get(tr, 0, r-1, p, u, q, v);
}
/*
int main()
{
int r1, c1, q;
cin >> r1 >> c1 >> q;
init(r1, c1);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int p, q;
long long k;
cin >> p >> q >> k;
update(p, q, k);
}
else
{
int p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << endl;
}
}
}
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
