#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
int maxn;
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;
}
struct treap_node
{
ll val, gcd;
int key, prio;
treap_node *left, *right;
treap_node(int _key, ll _val)
{
val = gcd = _val;
key = _key;
prio = (rand()<<16)^rand();
left = right = NULL;
}
void calc()
{
gcd = val;
if(left) gcd = gcd2(gcd, left->gcd);
if(right) gcd = gcd2(gcd, right->gcd);
}
};
treap_node* merge(treap_node *L, treap_node *R)
{
if(!L || !R) return L?L:R;
if(L->prio > R->prio)
{
L->right = merge(L->right, R);
L->calc();
return L;
}
else
{
R->left = merge(L, R->left);
R->calc();
return R;
}
}
void split(treap_node *big, treap_node* &L, treap_node* &R, int key)
{
L = R = NULL;
if(!big)
{
return;
}
if(big->key<= key)
{
L = big;
split(big->right, big->right, R, key);
}
else
{
R = big;
split(big->left, L, big->left, key);
}
big->calc();
}
ll ask_treap(int i, int j, treap_node* &u)
{
treap_node *one, *two;
split(u, one, u, i-1);
split(u, u, two, j);
ll ret = u?u->gcd:0;
u = merge(one, u);
u = merge(u, two);
return ret;
}
void upd_treap(treap_node* &u, int x, ll val)
{
treap_node *one, *two;
split(u, one, u, x-1);
split(u, u, two, x);
if(!u)
{
u = new treap_node(x, val);
}
else
{
assert(!(u->left));
assert(!(u->right));
u->key = u->gcd = val;
}
u = merge(one, u);
u = merge(u, two);
}
struct node
{
treap_node *x;
node *left, *right;
node()
{
x = NULL;
left = right = NULL;
}
node* getL()
{
if(left) return left;
return left = new node();
}
node* getR()
{
if(right) return right;
return right = new node();
}
};
ll ask(node *u, int i1, int j1, int i2, int j2, int L = 0, int R = maxn-1)
{
if(!u) return 0;
if(i1> R || i2< L) return 0;
if(i1<= L && R<= i2)
{
treap_node *one, *two;
split(u->x, one, u->x, j1-1);
split(u->x, u->x, two, j2);
ll ret = u->x?u->x->gcd:0;
u->x = merge(one, u->x);
u->x = merge(u->x, two);
return ret;
}
ll x = ask(u->left, i1, j1, i2, j2, L, (L+R)/2);
ll y = ask(u->right, i1, j1, i2, j2, (L+R)/2+1, R);
return gcd2(x, y);
}
void Update(node *u, int x, int y, ll val, int L = 0, int R = maxn-1)
{
treap_node *one, *two;
split(u->x, one, u->x, y-1);
split(u->x, u->x, two, y);
if(!(u->x))
{
u->x = new treap_node(y, val);
}
else
{
assert(!(u->x->left));
assert(!(u->x->right));
u->x->val = u->x->gcd = val;
}
u->x = merge(one, u->x);
u->x = merge(u->x, two);
if(L == R) return;
int M = (L+R)/2;
if(x<= M) Update(u->getL(), x, y, val, L, M);
else Update(u->getR(), x, y, val, M+1, R);
}
node *root;
void init(int R, int C)
{
srand(time(NULL));
maxn = R;
root = new node();
}
void update(int P, int Q, long long K)
{
Update(root, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return ask(root, P, Q, U, V);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
404 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
252 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
