#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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{
struct node{
int pos, prior;
ll val, res;
node *lef, *rig;
node(int p = 0, ll v = 0){
pos = p;
prior = rand();
val = v;
res = v;
lef = NULL;
rig = NULL;
}
};
typedef node *pnode;
pnode root;
treap(){
root = NULL;
}
void upd(pnode t){
if (t == NULL)
return;
t->res = t->val;
if (t->lef != NULL)
t->res = gcd2(t->res, t->lef->res);
if (t->rig != NULL)
t->res = gcd2(t->res, t->rig->res);
}
void split(pnode t, pnode &l, pnode &r, int k){
if (t == NULL)
return void(l = r = NULL);
if (t->pos <= k)
split(t->rig, t->rig, r, k), l = t;
else
split(t->lef, l, t->lef, k), r = t;
upd(t);
}
void join(pnode &t, pnode l, pnode r){
if (l == NULL)
return void(t = r);
if (r == NULL)
return void(t = l);
if (l->prior > r->prior)
join(l->rig, l->rig, r), t = l;
else
join(r->lef, l, r->lef), t = r;
upd(t);
}
void add(int p, ll v){
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, p);
split(l, l, mid, p-1);
mid = new node(p, v);
join(l, l, mid);
join(root, l, r);
}
ll ask(int a, int b){
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, b);
split(l, l, mid, a-1);
ll ans = NULL;
if (mid != NULL)
ans = mid->res;
join(l, l, mid);
join(root, l, r);
return ans;
}
void print(pnode t){
if (t == NULL)
return;
print(t->lef);
printf(" (%d, %lld)", t->pos, t->val);
print(t->rig);
}
void print(){
printf("treap now:");
print(root);
printf("\n");
}
};
struct seg_tree{
struct node{
treap tree;
node *lef, *rig;
node(node *l = NULL, node *r = NULL){
tree = treap();
lef = l;
rig = r;
}
};
typedef node *pnode;
pnode root, null;
int mx;
seg_tree(int m = 0){
null = new node();
null->lef = null->rig = null;
root = null;
mx = m;
}
pnode update(pnode t, int l, int r, int i, int j, ll v){
if (t == null)
t = new node(null, null);
t->tree.add(j, v);
if (l == r)
return t;
int mid = (l+r)/2;
if (i <= mid)
t->lef = update(t->lef, l, mid, i, j, v);
else
t->rig = update(t->rig, mid+1, r, i, j, v);
return t;
}
void add(int r, int c, ll v){
//printf("seg_tree::making (%d, %d) = %lld\n", r, c, v);
root = update(root, 0, mx-1, r, c, v);
//printf("now root: %lld\n", query(root, 0, mx-1, 0, mx-1, 0, 1000000));
}
ll query(pnode t, int l, int r, int i, int j, int a, int b){
if (r < i || j < l)
return 0;
if (i <= l && r <= j){
//printf("query, l = %d, r = %d, i = %d, j = %d\n", l, r, i, j);
//t->tree.print();
return t->tree.ask(a, b);
}
int mid = (l+r)/2;
return gcd2(query(t->lef, l, mid, i, j, a, b), query(t->rig, mid+1, r, i, j, a, b));
}
ll ask(int ar, int br, int ac, int bc){
//printf("seg_tree::asking for (%d, %d) and (%d, %d)\n", ar, br, ac, bc);
return query(root, 0, mx-1, ar, br, ac, bc);
}
};
seg_tree data;
void init(int R, int C) {
data = seg_tree(R);
/*treap test;
int q = 10;
printf("you are allowed to ask up to %d questions\n", q);
while (q--){
int tp;
scanf("%d", &tp);
// tp == 1 - add
// tp == 0 - ask
if (tp == 1){
int p;
ll v;
scanf("%d %lld", &p, &v);
test.add(p, v);
test.print();
}
else{
int l, r;
scanf("%d %d", &l, &r);
printf("res: %lld\n", test.ask(l, r));
}
}*/
}
void update(int P, int Q, long long K) {
data.add(P, Q, K);
}
long long calculate(int ar, int ac, int br, int bc) {
return data.ask(ar, br, ac, bc);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
game.cpp: In member function 'll treap::ask(int, int)':
game.cpp:97:18: warning: converting to non-pointer type 'll' {aka 'long long int'} from NULL [-Wconversion-null]
97 | ll ans = NULL;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
