#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N,M;
int T=0;
struct node{
ll v=0;
int p=0,l=0,r=0;
}S[20000005];
struct Segtree{
int root=0;
ll update(int l,int r,int &id,int x,ll val){
if(r<x || x<l) return (id?S[id].v:0);
if(!id){
id=++T,S[id].p=x;
return S[id].v=val;
}
if(l==r) return S[id].v=val;
int mid=(l+r)>>1;
if(S[id].p) update(l,mid,S[id].l,S[id].p,S[id].v),update(mid+1,r,S[id].r,S[id].p,S[id].v),S[id].p=0;
return S[id].v=__gcd(update(l,mid,S[id].l,x,val),update(mid+1,r,S[id].r,x,val));
}
ll query(int l,int r,int id,int tl,int tr){
if(tr<l || r<tl || !id) return 0;
if(tl<=l && r<=tr) return S[id].v;
if(S[id].p) return ((tl<=S[id].p && S[id].p<=tr)?S[id].v:0);
int mid=(l+r)>>1;
return __gcd(query(l,mid,S[id].l,tl,tr),query(mid+1,r,S[id].r,tl,tr));
};
};
int T2=0;
struct Node{
Segtree *s;
int l=0,r=0;
}S2[1000005];
struct Segtree2{
int root=0;
ll update(int l,int r,int &id,int x,int y,ll val){
if(r<x || x<l) return (id?S2[id].s->query(1,M,S2[id].s->root,y,y):0);
if(!id) S2[id=++T2].s=new Segtree();
if(l==r){
S2[id].s->update(1,M,S2[id].s->root,y,val);
return val;
}
int mid=(l+r)>>1;
val=__gcd(update(l,mid,S2[id].l,x,y,val),update(mid+1,r,S2[id].r,x,y,val));
S2[id].s->update(1,M,S2[id].s->root,y,val);
return val;
}
ll query(int l,int r,int id,int x,int y,int u,int v){
if(r<x || u<l || !id) return 0;
if(x<=l && r<=u) return S2[id].s->query(1,M,S2[id].s->root,y,v);
int mid=(l+r)>>1;
return __gcd(query(l,mid,S2[id].l,x,y,u,v),query(mid+1,r,S2[id].r,x,y,u,v));
}
}ST;
void init(int _N,int _M){
N=_N;M=_M;
}
void update(int P, int Q, ll K) {
P++;Q++;
ST.update(1,N,ST.root,P,Q,K);
}
ll calculate(int P, int Q, int U, int V) {
P++;Q++;U++;V++;
return ST.query(1,N,ST.root,P,Q,U,V);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16984 KB |
Output is correct |
2 |
Correct |
2 ms |
16988 KB |
Output is correct |
3 |
Correct |
2 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16988 KB |
Output is correct |
5 |
Correct |
2 ms |
16988 KB |
Output is correct |
6 |
Correct |
2 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16988 KB |
Output is correct |
8 |
Correct |
2 ms |
16988 KB |
Output is correct |
9 |
Correct |
2 ms |
17012 KB |
Output is correct |
10 |
Correct |
2 ms |
17236 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
2 ms |
16988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16984 KB |
Output is correct |
2 |
Correct |
2 ms |
16988 KB |
Output is correct |
3 |
Correct |
2 ms |
16988 KB |
Output is correct |
4 |
Correct |
256 ms |
25492 KB |
Output is correct |
5 |
Correct |
186 ms |
25680 KB |
Output is correct |
6 |
Correct |
239 ms |
22612 KB |
Output is correct |
7 |
Correct |
257 ms |
21848 KB |
Output is correct |
8 |
Correct |
196 ms |
22872 KB |
Output is correct |
9 |
Correct |
257 ms |
22316 KB |
Output is correct |
10 |
Correct |
238 ms |
21896 KB |
Output is correct |
11 |
Correct |
2 ms |
16984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16988 KB |
Output is correct |
2 |
Correct |
2 ms |
17020 KB |
Output is correct |
3 |
Correct |
2 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
16988 KB |
Output is correct |
5 |
Correct |
2 ms |
16988 KB |
Output is correct |
6 |
Correct |
2 ms |
17012 KB |
Output is correct |
7 |
Correct |
2 ms |
16984 KB |
Output is correct |
8 |
Correct |
3 ms |
16988 KB |
Output is correct |
9 |
Correct |
2 ms |
16984 KB |
Output is correct |
10 |
Correct |
2 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
17028 KB |
Output is correct |
12 |
Correct |
395 ms |
27536 KB |
Output is correct |
13 |
Correct |
664 ms |
22096 KB |
Output is correct |
14 |
Correct |
155 ms |
20048 KB |
Output is correct |
15 |
Correct |
738 ms |
24364 KB |
Output is correct |
16 |
Correct |
99 ms |
26328 KB |
Output is correct |
17 |
Correct |
407 ms |
23040 KB |
Output is correct |
18 |
Correct |
559 ms |
27144 KB |
Output is correct |
19 |
Correct |
524 ms |
27216 KB |
Output is correct |
20 |
Correct |
493 ms |
26704 KB |
Output is correct |
21 |
Correct |
2 ms |
16988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16988 KB |
Output is correct |
2 |
Correct |
2 ms |
16988 KB |
Output is correct |
3 |
Correct |
3 ms |
16988 KB |
Output is correct |
4 |
Correct |
2 ms |
17036 KB |
Output is correct |
5 |
Correct |
2 ms |
16988 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
16988 KB |
Output is correct |
8 |
Correct |
2 ms |
16988 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
2 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
263 ms |
25428 KB |
Output is correct |
13 |
Correct |
171 ms |
25680 KB |
Output is correct |
14 |
Correct |
243 ms |
22612 KB |
Output is correct |
15 |
Correct |
248 ms |
21912 KB |
Output is correct |
16 |
Correct |
184 ms |
22868 KB |
Output is correct |
17 |
Correct |
256 ms |
22380 KB |
Output is correct |
18 |
Correct |
221 ms |
22108 KB |
Output is correct |
19 |
Correct |
389 ms |
27460 KB |
Output is correct |
20 |
Correct |
616 ms |
22100 KB |
Output is correct |
21 |
Correct |
156 ms |
20048 KB |
Output is correct |
22 |
Correct |
727 ms |
24404 KB |
Output is correct |
23 |
Correct |
119 ms |
26320 KB |
Output is correct |
24 |
Correct |
394 ms |
23124 KB |
Output is correct |
25 |
Correct |
566 ms |
26960 KB |
Output is correct |
26 |
Correct |
531 ms |
27312 KB |
Output is correct |
27 |
Correct |
465 ms |
26536 KB |
Output is correct |
28 |
Correct |
250 ms |
44988 KB |
Output is correct |
29 |
Correct |
555 ms |
43856 KB |
Output is correct |
30 |
Correct |
1883 ms |
40784 KB |
Output is correct |
31 |
Correct |
1817 ms |
60860 KB |
Output is correct |
32 |
Correct |
286 ms |
22352 KB |
Output is correct |
33 |
Correct |
403 ms |
24456 KB |
Output is correct |
34 |
Correct |
128 ms |
38996 KB |
Output is correct |
35 |
Correct |
493 ms |
32448 KB |
Output is correct |
36 |
Correct |
762 ms |
41548 KB |
Output is correct |
37 |
Correct |
680 ms |
41556 KB |
Output is correct |
38 |
Correct |
698 ms |
41000 KB |
Output is correct |
39 |
Correct |
556 ms |
35820 KB |
Output is correct |
40 |
Correct |
2 ms |
16984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16988 KB |
Output is correct |
2 |
Correct |
2 ms |
16988 KB |
Output is correct |
3 |
Correct |
2 ms |
16992 KB |
Output is correct |
4 |
Correct |
2 ms |
16988 KB |
Output is correct |
5 |
Correct |
2 ms |
16988 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
2 ms |
17244 KB |
Output is correct |
8 |
Correct |
2 ms |
16988 KB |
Output is correct |
9 |
Correct |
2 ms |
16988 KB |
Output is correct |
10 |
Correct |
2 ms |
16988 KB |
Output is correct |
11 |
Correct |
2 ms |
16988 KB |
Output is correct |
12 |
Correct |
250 ms |
25488 KB |
Output is correct |
13 |
Correct |
179 ms |
25644 KB |
Output is correct |
14 |
Correct |
238 ms |
22464 KB |
Output is correct |
15 |
Correct |
272 ms |
21844 KB |
Output is correct |
16 |
Correct |
184 ms |
22864 KB |
Output is correct |
17 |
Correct |
285 ms |
22472 KB |
Output is correct |
18 |
Correct |
237 ms |
22100 KB |
Output is correct |
19 |
Correct |
432 ms |
27472 KB |
Output is correct |
20 |
Correct |
680 ms |
22100 KB |
Output is correct |
21 |
Correct |
145 ms |
19904 KB |
Output is correct |
22 |
Correct |
836 ms |
24336 KB |
Output is correct |
23 |
Correct |
120 ms |
26264 KB |
Output is correct |
24 |
Correct |
426 ms |
22868 KB |
Output is correct |
25 |
Correct |
609 ms |
27092 KB |
Output is correct |
26 |
Correct |
534 ms |
27216 KB |
Output is correct |
27 |
Correct |
453 ms |
26464 KB |
Output is correct |
28 |
Correct |
255 ms |
45196 KB |
Output is correct |
29 |
Correct |
574 ms |
43668 KB |
Output is correct |
30 |
Correct |
1827 ms |
40700 KB |
Output is correct |
31 |
Correct |
1765 ms |
60692 KB |
Output is correct |
32 |
Correct |
269 ms |
22344 KB |
Output is correct |
33 |
Correct |
377 ms |
24408 KB |
Output is correct |
34 |
Correct |
126 ms |
39048 KB |
Output is correct |
35 |
Correct |
448 ms |
32340 KB |
Output is correct |
36 |
Correct |
696 ms |
39120 KB |
Output is correct |
37 |
Correct |
629 ms |
36180 KB |
Output is correct |
38 |
Correct |
617 ms |
35408 KB |
Output is correct |
39 |
Correct |
350 ms |
76528 KB |
Output is correct |
40 |
Correct |
844 ms |
68176 KB |
Output is correct |
41 |
Correct |
2237 ms |
68048 KB |
Output is correct |
42 |
Correct |
2278 ms |
107624 KB |
Output is correct |
43 |
Correct |
215 ms |
62924 KB |
Output is correct |
44 |
Correct |
399 ms |
27120 KB |
Output is correct |
45 |
Correct |
573 ms |
40816 KB |
Output is correct |
46 |
Correct |
905 ms |
67084 KB |
Output is correct |
47 |
Correct |
884 ms |
66956 KB |
Output is correct |
48 |
Correct |
856 ms |
66644 KB |
Output is correct |
49 |
Correct |
2 ms |
16988 KB |
Output is correct |