#include "game.h"
#include <iostream>
#include <algorithm>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
ll gcd(ll x, ll y) {
if(x < y)
swap(x, y);
while(y){
x %= y;
swap(x, y);
}
return x;
}
int n, m, dl, dr;
struct node{
node* p[2] = {nullptr, nullptr};
node* p1[2] = {nullptr, nullptr};
ll val = 0;
node* getp(int v){
if(!p[v])
p[v] = new node;
return p[v];
}
node* getp1(int v){
if(!p1[v])
p1[v] = new node;
return p1[v];
}
void merge(int tl, int tr, node* L, node* R, int pos){
if(!L && !R)
return;
if(tl == tr){
val = 0;
if(L)
val = gcd(L->val, val);
if(R)
val = gcd(R->val, val);
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm){
if(L)
L = L->p1[0];
if(R)
R = R->p1[0];
getp1(0)->merge(tl, tm, L, R, pos);
}
else{
if(L)
L = L->p1[1];
if(R)
R = R->p1[1];
getp1(1)->merge(tm + 1, tr, L, R, pos);
}
val = 0;
if(p1[0])
val = gcd(p1[0]->val, val);
if(p1[1])
val = gcd(p1[1]->val, val);
//cerr << tl << " " << tr << " " << val << " " << this << "s\n";
}
void upd1(int tl, int tr, int pos, ll _val){
if(tl == tr)
return void(val = _val);
int tm = (tl + tr) / 2;
//cerr << tl << " s " << tr << "\n";
if(pos <= tm)
getp1(0)->upd1(tl, tm, pos, _val);
else
getp1(1)->upd1(tm + 1, tr, pos, _val);
val = 0;
if(p1[0])
val = gcd(p1[0]->val, val);
if(p1[1])
val = gcd(p1[1]->val, val);
}
ll get1(int tl, int tr, int l, int r){
if(tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return val;
int tm = (tl + tr) / 2;
ll left = (p1[0] ? p1[0]->get1(tl, tm, l, r): 0);
ll right = (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0);
return gcd(left, right);
}
void upd(int tl, int tr, int pos, ll _val){
//cerr << tl << " " << tr << " b " << this << "\n";
if(tl == tr){
return void(upd1(1, m, dl, _val));
}
int tm = (tl + tr) / 2;
if(pos <= tm)
getp(0)->upd(tl, tm, pos, _val);
else
getp(1)->upd(tm + 1, tr, pos, _val);
merge(1, m, p[0], p[1], dl);
}
ll get(int tl, int tr, int l, int r){
if(tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return get1(1, m, dl, dr);
int tm = (tl + tr) / 2;
ll left = (p[0] ? p[0]->get(tl, tm, l, r): 0);
ll right = (p[1] ? p[1]->get(tm + 1, tr, l, r): 0);
//cerr << tl << " " << tr << " " << left << " z " << right << "\n";
return gcd(left, right);
}
}root;
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, ll K) {
// cerr << "was1\n";
dl = Q + 1;
//cerr << P + 1 << " " << Q + 1 << "\n";
root.upd(1, n, P + 1, K);
// cerr << "was\n";
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
//cerr << "were\n";
dl = Q + 1, dr = V + 1;
//cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n";
ll tmp = root.get(1, n, P + 1, U + 1);
// cerr << tmp << "\n";
return tmp;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
272 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
623 ms |
21136 KB |
Output is correct |
5 |
Correct |
426 ms |
20932 KB |
Output is correct |
6 |
Correct |
526 ms |
18740 KB |
Output is correct |
7 |
Correct |
581 ms |
18388 KB |
Output is correct |
8 |
Correct |
424 ms |
13284 KB |
Output is correct |
9 |
Correct |
588 ms |
18536 KB |
Output is correct |
10 |
Correct |
539 ms |
18232 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
958 ms |
25612 KB |
Output is correct |
13 |
Correct |
1347 ms |
12528 KB |
Output is correct |
14 |
Correct |
282 ms |
5696 KB |
Output is correct |
15 |
Correct |
1531 ms |
16724 KB |
Output is correct |
16 |
Correct |
226 ms |
30820 KB |
Output is correct |
17 |
Correct |
1004 ms |
21056 KB |
Output is correct |
18 |
Correct |
1496 ms |
32500 KB |
Output is correct |
19 |
Correct |
1298 ms |
32464 KB |
Output is correct |
20 |
Correct |
1218 ms |
31764 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
428 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
552 ms |
21120 KB |
Output is correct |
13 |
Correct |
408 ms |
20932 KB |
Output is correct |
14 |
Correct |
550 ms |
18708 KB |
Output is correct |
15 |
Correct |
604 ms |
18404 KB |
Output is correct |
16 |
Correct |
379 ms |
13244 KB |
Output is correct |
17 |
Correct |
563 ms |
18628 KB |
Output is correct |
18 |
Correct |
532 ms |
18144 KB |
Output is correct |
19 |
Correct |
867 ms |
25540 KB |
Output is correct |
20 |
Correct |
1316 ms |
12540 KB |
Output is correct |
21 |
Correct |
291 ms |
5696 KB |
Output is correct |
22 |
Correct |
1618 ms |
16768 KB |
Output is correct |
23 |
Correct |
229 ms |
30784 KB |
Output is correct |
24 |
Correct |
927 ms |
21072 KB |
Output is correct |
25 |
Correct |
1559 ms |
32392 KB |
Output is correct |
26 |
Correct |
1368 ms |
32344 KB |
Output is correct |
27 |
Correct |
1245 ms |
31828 KB |
Output is correct |
28 |
Runtime error |
656 ms |
256004 KB |
Execution killed with signal 9 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
464 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
567 ms |
21100 KB |
Output is correct |
13 |
Correct |
412 ms |
20988 KB |
Output is correct |
14 |
Correct |
518 ms |
18740 KB |
Output is correct |
15 |
Correct |
593 ms |
18460 KB |
Output is correct |
16 |
Correct |
446 ms |
13248 KB |
Output is correct |
17 |
Correct |
563 ms |
18588 KB |
Output is correct |
18 |
Correct |
518 ms |
18072 KB |
Output is correct |
19 |
Correct |
929 ms |
25492 KB |
Output is correct |
20 |
Correct |
1388 ms |
12716 KB |
Output is correct |
21 |
Correct |
298 ms |
5868 KB |
Output is correct |
22 |
Correct |
1531 ms |
16700 KB |
Output is correct |
23 |
Correct |
242 ms |
30884 KB |
Output is correct |
24 |
Correct |
951 ms |
21160 KB |
Output is correct |
25 |
Correct |
1538 ms |
32504 KB |
Output is correct |
26 |
Correct |
1379 ms |
32400 KB |
Output is correct |
27 |
Correct |
1221 ms |
31904 KB |
Output is correct |
28 |
Runtime error |
741 ms |
256004 KB |
Execution killed with signal 9 |
29 |
Halted |
0 ms |
0 KB |
- |