#include "game.h"
#include <cstdio>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
inline long long func(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ii lca(int s,int e,int l,int r,int pos){
int m=s+e>>1;
if (r<=m && m<pos) return ii(s,e);
else if (pos<=m && m<l) return ii(s,e);
if (pos<=m) return lca(s,m,l,r,pos);
else return lca(m+1,e,l,r,pos);
}
struct node{
int s,e,m;
long long val=0;
node *l=nullptr,*r=nullptr;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,long long j){
if (s==e) val=j;
else{
if (i<=m){
if (l==nullptr) l=new node(i,i);
else if (!l->inside(i)){
node *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new node(child.first,child.second);
if (temp->e<=l->m) l->l=temp;
else l->r=temp;
}
l->update(i,j);
}
else{
if (r==nullptr) r=new node(i,i);
else if (!r->inside(i)){
node *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new node(child.first,child.second);
if (temp->e<=r->m) r->l=temp;
else r->r=temp;
}
r->update(i,j);
}
val=func((l==nullptr)?0:l->val,(r==nullptr)?0:r->val);
}
}
long long query(int i,int j){
if (i<=s && e<=j) return val;
else if (j<=m) return (l==nullptr)?0:l->query(i,j);
else if (m<i) return (r==nullptr)?0:r->query(i,j);
else return func((l==nullptr)?0:l->query(i,m),(r==nullptr)?0:r->query(m+1,j));
}
node* clone(){
node* res=new node(s,e);
res->val=val;
res->l=(l==nullptr)?nullptr:l->clone();
res->r=(r==nullptr)?nullptr:r->clone();
return res;
}
};
struct node2d{
int s,e,m;
node *val=new node(0,1000000000);
node2d *l=nullptr,*r=nullptr;
node2d (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,int j,long long k){
if (s==e) val->update(j,k);
else{
if (i<=m){
if (l==nullptr) l=new node2d(i,i);
else if (!l->inside(i)){
node2d *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new node2d(child.first,child.second);
if (temp->e<=l->m) l->l=temp;
else l->r=temp;
l->val=temp->val->clone();
}
l->update(i,j,k);
}
else{
if (r==nullptr) r=new node2d(i,i);
else if (!r->inside(i)){
node2d *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new node2d(child.first,child.second);
if (temp->e<=r->m) r->l=temp;
else r->r=temp;
r->val=temp->val->clone();
}
r->update(i,j,k);
}
val->update(j,func((l==nullptr)?0:l->val->query(j,j),(r==nullptr)?0:r->val->query(j,j)));
}
}
long long query(int i,int j,int i2,int j2){
if (i<=s && e<=j) return val->query(i2,j2);
else if (j<=m) return (l==nullptr)?0:l->query(i,j,i2,j2);
else if (m<i) return (r==nullptr)?0:r->query(i,j,i2,j2);
else return func((l==nullptr)?0:l->query(i,m,i2,j2),(r==nullptr)?0:r->query(m+1,j,i2,j2));
}
}*root=new node2d(0,1000000000);
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
root->update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return root->query(P,U,Q,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;
^~~
game.cpp: In function 'ii lca(int, int, int, int, int)':
game.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
game.cpp: In constructor 'node::node(int, int)':
game.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
s=_s,e=_e,m=s+e>>1;
~^~
game.cpp: In constructor 'node2d::node2d(int, int)':
game.cpp:89:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
s=_s,e=_e,m=s+e>>1;
~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
576 ms |
14096 KB |
Output is correct |
5 |
Correct |
368 ms |
13816 KB |
Output is correct |
6 |
Correct |
654 ms |
11380 KB |
Output is correct |
7 |
Correct |
775 ms |
11000 KB |
Output is correct |
8 |
Correct |
464 ms |
8696 KB |
Output is correct |
9 |
Correct |
718 ms |
11108 KB |
Output is correct |
10 |
Correct |
587 ms |
10748 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
905 ms |
16084 KB |
Output is correct |
13 |
Correct |
1926 ms |
9228 KB |
Output is correct |
14 |
Correct |
276 ms |
5756 KB |
Output is correct |
15 |
Correct |
2211 ms |
10928 KB |
Output is correct |
16 |
Correct |
296 ms |
14840 KB |
Output is correct |
17 |
Correct |
1083 ms |
11744 KB |
Output is correct |
18 |
Correct |
1896 ms |
16376 KB |
Output is correct |
19 |
Correct |
1582 ms |
16496 KB |
Output is correct |
20 |
Correct |
1490 ms |
16072 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
565 ms |
14072 KB |
Output is correct |
13 |
Correct |
371 ms |
13868 KB |
Output is correct |
14 |
Correct |
646 ms |
11260 KB |
Output is correct |
15 |
Correct |
735 ms |
10872 KB |
Output is correct |
16 |
Correct |
457 ms |
8860 KB |
Output is correct |
17 |
Correct |
707 ms |
11088 KB |
Output is correct |
18 |
Correct |
588 ms |
10800 KB |
Output is correct |
19 |
Correct |
850 ms |
16140 KB |
Output is correct |
20 |
Correct |
1915 ms |
9176 KB |
Output is correct |
21 |
Correct |
274 ms |
5672 KB |
Output is correct |
22 |
Correct |
2189 ms |
10788 KB |
Output is correct |
23 |
Correct |
300 ms |
14796 KB |
Output is correct |
24 |
Correct |
1121 ms |
11720 KB |
Output is correct |
25 |
Correct |
1871 ms |
16296 KB |
Output is correct |
26 |
Correct |
1633 ms |
16496 KB |
Output is correct |
27 |
Correct |
1405 ms |
16056 KB |
Output is correct |
28 |
Correct |
559 ms |
26616 KB |
Output is correct |
29 |
Correct |
1536 ms |
28960 KB |
Output is correct |
30 |
Correct |
3869 ms |
20380 KB |
Output is correct |
31 |
Correct |
3555 ms |
17216 KB |
Output is correct |
32 |
Correct |
328 ms |
10124 KB |
Output is correct |
33 |
Correct |
508 ms |
10488 KB |
Output is correct |
34 |
Correct |
1126 ms |
22736 KB |
Output is correct |
35 |
Correct |
1193 ms |
18276 KB |
Output is correct |
36 |
Correct |
2336 ms |
26996 KB |
Output is correct |
37 |
Correct |
1906 ms |
27056 KB |
Output is correct |
38 |
Correct |
1763 ms |
26540 KB |
Output is correct |
39 |
Correct |
1547 ms |
23004 KB |
Output is correct |
40 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
252 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
558 ms |
14052 KB |
Output is correct |
13 |
Correct |
396 ms |
14008 KB |
Output is correct |
14 |
Correct |
653 ms |
11184 KB |
Output is correct |
15 |
Correct |
721 ms |
11080 KB |
Output is correct |
16 |
Correct |
450 ms |
8884 KB |
Output is correct |
17 |
Correct |
753 ms |
11232 KB |
Output is correct |
18 |
Correct |
589 ms |
10696 KB |
Output is correct |
19 |
Correct |
849 ms |
15984 KB |
Output is correct |
20 |
Correct |
1961 ms |
9312 KB |
Output is correct |
21 |
Correct |
278 ms |
5752 KB |
Output is correct |
22 |
Correct |
2230 ms |
10836 KB |
Output is correct |
23 |
Correct |
304 ms |
14968 KB |
Output is correct |
24 |
Correct |
1108 ms |
11980 KB |
Output is correct |
25 |
Correct |
2065 ms |
16432 KB |
Output is correct |
26 |
Correct |
1634 ms |
16616 KB |
Output is correct |
27 |
Correct |
1399 ms |
15988 KB |
Output is correct |
28 |
Correct |
587 ms |
26620 KB |
Output is correct |
29 |
Correct |
1699 ms |
28872 KB |
Output is correct |
30 |
Correct |
3878 ms |
20344 KB |
Output is correct |
31 |
Correct |
3569 ms |
17232 KB |
Output is correct |
32 |
Correct |
331 ms |
10160 KB |
Output is correct |
33 |
Correct |
495 ms |
10220 KB |
Output is correct |
34 |
Correct |
1112 ms |
22908 KB |
Output is correct |
35 |
Correct |
1274 ms |
18464 KB |
Output is correct |
36 |
Correct |
2288 ms |
26956 KB |
Output is correct |
37 |
Correct |
1837 ms |
27200 KB |
Output is correct |
38 |
Correct |
1744 ms |
26316 KB |
Output is correct |
39 |
Correct |
749 ms |
47312 KB |
Output is correct |
40 |
Correct |
2483 ms |
48516 KB |
Output is correct |
41 |
Correct |
5236 ms |
37520 KB |
Output is correct |
42 |
Correct |
4868 ms |
29436 KB |
Output is correct |
43 |
Correct |
1462 ms |
43332 KB |
Output is correct |
44 |
Correct |
390 ms |
10616 KB |
Output is correct |
45 |
Correct |
1587 ms |
22904 KB |
Output is correct |
46 |
Correct |
3302 ms |
47328 KB |
Output is correct |
47 |
Correct |
3324 ms |
47456 KB |
Output is correct |
48 |
Correct |
3022 ms |
46740 KB |
Output is correct |
49 |
Correct |
2 ms |
256 KB |
Output is correct |