#include <bits/stdc++.h>
#include "game.h"
typedef long long ll;
static int R, C;
ll gcd2(ll x, ll y) {
if (y == 0) return x;
return gcd2(y, x % y);
}
struct xnod{
xnod(int tl, int tr):tl(tl),tr(tr),l(NULL),r(NULL),value(0LL) {}
int tl,tr;
xnod *l,*r;
ll value;
};
struct ynod{
ynod():l(NULL),r(NULL),xst(1,C){}
ynod *l,*r;
xnod xst;
} *root;
void init(int r, int c)
{
R=r,C=c;
root=new ynod();
}
void update2(xnod *nod,int q,ll k) {
int tl=nod->tl,tr=nod->tr,m=(tl+tr)/2;
if (tl==tr) {
nod->value=k;
return;
}
xnod** koce=&(q<=m?nod->l:nod->r);
if (*koce==NULL) {
*koce=new xnod(q, q);
(*koce)->value = k;
} else if ((*koce)->tl <= q && q <= (*koce)->tr) {
update2(*koce, q, k);
} else {
do {
if (q <= m) tr = m;
else tl = m + 1;
m = (tl + tr) >> 1;
} while ((q <= m) == ((*koce)->tr <= m));
xnod *temp= new xnod(tl, tr);
if ((*koce)->tr <= m) temp->l = *koce;
else temp->r = *koce;
*koce = temp;
update2(*koce, q, k);
}
nod->value=gcd2(nod->l ? nod->l->value : 0, nod->r?nod->r->value : 0);
}
ll query2(xnod *node,int tl, int tr) {
if (node == NULL || node->tl > tr || node->tr < tl) return 0;
if (tl <= node->tl && node->tr <= tr) { return node->value; }
return gcd2(query2(node->l, tl, tr), query2(node->r, tl, tr));
}
void update1(ynod *node, int tl, int tr, int vx, int vy, ll k) {
int m = (tl + tr)/2;
if (tr == tl) {
update2(&node->xst, vy, k);
return;
}
if (vx <= m) {
if (node->l == NULL) node->l = new ynod();
update1(node->l, tl, m, vx, vy, k);
} else {
if (node->r == NULL) node->r = new ynod();
update1(node->r, m + 1, tr, vx, vy, k);
}
ll v = gcd2(node->l ? query2(&node->l->xst, vy, vy) : 0,node->r ? query2(&node->r->xst, vy, vy) : 0);
update2(&node->xst, vy, v);
}
void update(int vx, int vy, ll k) {
++vx, ++vy;
update1(root, 1, R, vx, vy, k);
}
ll query1(ynod *node, int tl, int tr, int vxl, int vyl, int vxr, int vyr) {
if (node == NULL || tl > vxr || tr < vxl) return 0;
if (vxl <= tl && tr<=vxr) return query2(&node->xst, vyl, vyr);
int m = (tl+tr)/2;
return gcd2(query1(node->l, tl, m, vxl, vyl, vxr, vyr),query1(node->r, m + 1, tr, vxl, vyl,vxr,vyr));
}
ll calculate(int vxl, int vyl, int vxr, int vyr) {
++vxl, ++vyl, ++vxr, ++vyr;
return query1(root, 1, R, vxl, vyl, vxr, vyr);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
436 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
436 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
326 ms |
12684 KB |
Output is correct |
5 |
Correct |
201 ms |
12624 KB |
Output is correct |
6 |
Correct |
280 ms |
10156 KB |
Output is correct |
7 |
Correct |
326 ms |
9772 KB |
Output is correct |
8 |
Correct |
210 ms |
7988 KB |
Output is correct |
9 |
Correct |
339 ms |
9812 KB |
Output is correct |
10 |
Correct |
289 ms |
9552 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
432 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
543 ms |
15640 KB |
Output is correct |
13 |
Correct |
870 ms |
9044 KB |
Output is correct |
14 |
Correct |
144 ms |
5716 KB |
Output is correct |
15 |
Correct |
998 ms |
10576 KB |
Output is correct |
16 |
Correct |
123 ms |
14164 KB |
Output is correct |
17 |
Correct |
460 ms |
11032 KB |
Output is correct |
18 |
Correct |
815 ms |
15560 KB |
Output is correct |
19 |
Correct |
688 ms |
15696 KB |
Output is correct |
20 |
Correct |
609 ms |
15076 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
313 ms |
12648 KB |
Output is correct |
13 |
Correct |
203 ms |
12628 KB |
Output is correct |
14 |
Correct |
305 ms |
10148 KB |
Output is correct |
15 |
Correct |
320 ms |
9812 KB |
Output is correct |
16 |
Correct |
213 ms |
8024 KB |
Output is correct |
17 |
Correct |
301 ms |
9896 KB |
Output is correct |
18 |
Correct |
293 ms |
9552 KB |
Output is correct |
19 |
Correct |
527 ms |
15516 KB |
Output is correct |
20 |
Correct |
899 ms |
8792 KB |
Output is correct |
21 |
Correct |
145 ms |
5716 KB |
Output is correct |
22 |
Correct |
972 ms |
10576 KB |
Output is correct |
23 |
Correct |
114 ms |
14160 KB |
Output is correct |
24 |
Correct |
497 ms |
11068 KB |
Output is correct |
25 |
Correct |
787 ms |
15444 KB |
Output is correct |
26 |
Correct |
672 ms |
15596 KB |
Output is correct |
27 |
Correct |
647 ms |
15168 KB |
Output is correct |
28 |
Correct |
280 ms |
43340 KB |
Output is correct |
29 |
Correct |
880 ms |
45424 KB |
Output is correct |
30 |
Correct |
1412 ms |
35312 KB |
Output is correct |
31 |
Correct |
1222 ms |
28568 KB |
Output is correct |
32 |
Correct |
236 ms |
10320 KB |
Output is correct |
33 |
Correct |
292 ms |
10836 KB |
Output is correct |
34 |
Correct |
158 ms |
39248 KB |
Output is correct |
35 |
Correct |
621 ms |
27068 KB |
Output is correct |
36 |
Correct |
1101 ms |
43320 KB |
Output is correct |
37 |
Correct |
953 ms |
43364 KB |
Output is correct |
38 |
Correct |
899 ms |
43132 KB |
Output is correct |
39 |
Correct |
815 ms |
35748 KB |
Output is correct |
40 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
326 ms |
12724 KB |
Output is correct |
13 |
Correct |
203 ms |
12720 KB |
Output is correct |
14 |
Correct |
284 ms |
10068 KB |
Output is correct |
15 |
Correct |
326 ms |
9808 KB |
Output is correct |
16 |
Correct |
210 ms |
8068 KB |
Output is correct |
17 |
Correct |
308 ms |
9808 KB |
Output is correct |
18 |
Correct |
297 ms |
9556 KB |
Output is correct |
19 |
Correct |
538 ms |
15696 KB |
Output is correct |
20 |
Correct |
907 ms |
8792 KB |
Output is correct |
21 |
Correct |
168 ms |
5644 KB |
Output is correct |
22 |
Correct |
987 ms |
10596 KB |
Output is correct |
23 |
Correct |
115 ms |
14128 KB |
Output is correct |
24 |
Correct |
453 ms |
11112 KB |
Output is correct |
25 |
Correct |
846 ms |
15500 KB |
Output is correct |
26 |
Correct |
663 ms |
15580 KB |
Output is correct |
27 |
Correct |
616 ms |
15112 KB |
Output is correct |
28 |
Correct |
281 ms |
43304 KB |
Output is correct |
29 |
Correct |
872 ms |
45396 KB |
Output is correct |
30 |
Correct |
1428 ms |
35200 KB |
Output is correct |
31 |
Correct |
1252 ms |
28500 KB |
Output is correct |
32 |
Correct |
231 ms |
10220 KB |
Output is correct |
33 |
Correct |
294 ms |
10700 KB |
Output is correct |
34 |
Correct |
160 ms |
39092 KB |
Output is correct |
35 |
Correct |
584 ms |
26912 KB |
Output is correct |
36 |
Correct |
1111 ms |
43308 KB |
Output is correct |
37 |
Correct |
905 ms |
43488 KB |
Output is correct |
38 |
Correct |
918 ms |
42832 KB |
Output is correct |
39 |
Correct |
416 ms |
81236 KB |
Output is correct |
40 |
Correct |
1422 ms |
81996 KB |
Output is correct |
41 |
Correct |
1787 ms |
67152 KB |
Output is correct |
42 |
Correct |
1677 ms |
52528 KB |
Output is correct |
43 |
Correct |
299 ms |
76744 KB |
Output is correct |
44 |
Correct |
274 ms |
10844 KB |
Output is correct |
45 |
Correct |
745 ms |
35664 KB |
Output is correct |
46 |
Correct |
1521 ms |
80976 KB |
Output is correct |
47 |
Correct |
1512 ms |
80872 KB |
Output is correct |
48 |
Correct |
1447 ms |
80564 KB |
Output is correct |
49 |
Correct |
1 ms |
348 KB |
Output is correct |