# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
330500 |
2020-11-25T15:00:14 Z |
zggf |
Game (IOI13_game) |
C++14 |
|
1854 ms |
256004 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
long long pot (long long x){
long long tmp = 1;
while(x){
x/=2;
tmp*=2;
}
return tmp;
}
long long treeSizeX, treeSizeY;
struct node{
node *right = nullptr, *left = nullptr;
long long val = 0;
};
struct tree{
tree *left = nullptr, *right = nullptr;
node *root = nullptr;
};
void malyUpdate(long long v, long long a, node *rt, long long q = 0, long long r = treeSizeX-1){
//cout<<q<<" "<<r<<" "<<rt->val<<endl;
if(q==r){
rt->val = v;
return;
}
long long mid = (q+r)/2;
if(a<=mid){
if(rt->left==nullptr) rt->left = new node();
malyUpdate(v, a, rt->left, q, mid);
rt->val = rt->left->val;
if(rt->right!=nullptr) rt->val = gcd2(rt->val, rt->right->val);
}
if(a>mid){
if(rt->right==nullptr) rt->right = new node();
malyUpdate(v, a,rt->right, mid+1, r);
rt->val = rt->right->val;
if(rt->left!=nullptr) rt->val = gcd2(rt->val, rt->left->val);
}
}
void sredniUpdate(long long a, node *rt1, node *rt2, node *rt4, long long q = 0, long long r = treeSizeX-1){
if(q==r){
rt4->val = gcd2(rt1->val, rt2==nullptr?0:rt2->val);
return;
}
long long mid = (q+r)/2;
if(a<=mid){
if(rt4->left==nullptr) rt4->left = new node();
sredniUpdate(a, rt1->left, rt2==nullptr?nullptr:rt2->left, rt4->left, q, mid);
}
if(a>mid){
if(rt4->right==nullptr) rt4->right = new node();
sredniUpdate(a, rt1->right, rt2==nullptr?nullptr:rt2->right, rt4->right, mid+1, r);
}
rt4->val = rt1->val;
if(rt2!=nullptr) rt4->val = gcd2(rt1->val, rt2->val);
}
tree *drzewo;
void duzyUpdate(long long v, long long x, long long y, long long q = 0, long long r = treeSizeY-1, tree *rt = drzewo){
if(rt->root==nullptr) rt->root = new node();
if(q==r){
malyUpdate(v, x, rt->root);
return;
}
long long mid = (q+r)/2;
if(y<=mid){
if(rt->left==nullptr) rt->left = new tree();
duzyUpdate(v, x, y, q, mid, rt->left);
sredniUpdate(x, rt->left->root, rt->right==nullptr?nullptr:rt->right->root, rt->root);
}else{
if(rt->right==nullptr) rt->right = new tree();
duzyUpdate(v, x, y, mid+1, r, rt->right);
sredniUpdate(x, rt->right->root, rt->left==nullptr?nullptr:rt->left->root, rt->root);
}
}
long long malyQur(long long a, long long b, node *rt, long long q = 0, long long r = treeSizeX-1){
//cout<<q<<" "<<r<<" "<<rt->val<<endl;
if(a==q&&b==r){
return rt->val;
}
long long mid = (q+r)/2;
long long out = 0;
if(a<=mid){
if(rt->left!=nullptr){
out = malyQur(a, min(b, mid), rt->left, q, mid);
}
}
if(b>mid){
if(rt->right!=nullptr){
out = gcd2(out, malyQur(max(a, mid+1), b, rt->right, mid+1, r));
}
}
return out;
}
long long duzyQur(long long x1, long long x2, long long y1, long long y2, tree *rt, long long q = 0, long long r = treeSizeY-1){
//cout<<q<<" "<<r<<" "<<y1<<"-"<<y2<<endl;
if(y1==q&&y2==r){
return malyQur(x1, x2, rt->root);
}
long long out = 0;
long long mid = (q+r)/2;
if(y1<=mid){
if(rt->left!=nullptr){
out = duzyQur(x1, x2, y1, min(y2, mid), rt->left, q, mid);
}
}
if(y2>mid){
if(rt->right!=nullptr){
out = gcd2(out, duzyQur(x1, x2, max(y1, mid+1), y2, rt->right, mid+1, r));
}
}
return out;
}
void init(int R, int C) {
swap(R, C);
treeSizeY = pot(R);
treeSizeX = pot(C);
drzewo = new tree();
}
void update(int P, int Q, long long K) {
duzyUpdate(K, P, Q);
}
long long calculate(int P, int Q, int U, int V) {
return duzyQur(P, U, Q, V, drzewo);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
535 ms |
19484 KB |
Output is correct |
5 |
Correct |
451 ms |
19436 KB |
Output is correct |
6 |
Correct |
657 ms |
16960 KB |
Output is correct |
7 |
Correct |
806 ms |
16696 KB |
Output is correct |
8 |
Correct |
470 ms |
12268 KB |
Output is correct |
9 |
Correct |
800 ms |
16756 KB |
Output is correct |
10 |
Correct |
737 ms |
16388 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
376 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
858 ms |
19948 KB |
Output is correct |
13 |
Correct |
1392 ms |
10112 KB |
Output is correct |
14 |
Correct |
308 ms |
5740 KB |
Output is correct |
15 |
Correct |
1581 ms |
13364 KB |
Output is correct |
16 |
Correct |
357 ms |
22488 KB |
Output is correct |
17 |
Correct |
922 ms |
16464 KB |
Output is correct |
18 |
Correct |
1640 ms |
23964 KB |
Output is correct |
19 |
Correct |
1304 ms |
24300 KB |
Output is correct |
20 |
Correct |
1236 ms |
23608 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
372 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
551 ms |
19436 KB |
Output is correct |
13 |
Correct |
466 ms |
19372 KB |
Output is correct |
14 |
Correct |
691 ms |
16992 KB |
Output is correct |
15 |
Correct |
798 ms |
16656 KB |
Output is correct |
16 |
Correct |
465 ms |
12396 KB |
Output is correct |
17 |
Correct |
766 ms |
16772 KB |
Output is correct |
18 |
Correct |
804 ms |
16620 KB |
Output is correct |
19 |
Correct |
864 ms |
19992 KB |
Output is correct |
20 |
Correct |
1394 ms |
10376 KB |
Output is correct |
21 |
Correct |
284 ms |
5892 KB |
Output is correct |
22 |
Correct |
1569 ms |
13420 KB |
Output is correct |
23 |
Correct |
365 ms |
22508 KB |
Output is correct |
24 |
Correct |
870 ms |
16492 KB |
Output is correct |
25 |
Correct |
1588 ms |
24064 KB |
Output is correct |
26 |
Correct |
1304 ms |
24208 KB |
Output is correct |
27 |
Correct |
1206 ms |
23472 KB |
Output is correct |
28 |
Correct |
1004 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1828 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
276 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
542 ms |
19564 KB |
Output is correct |
13 |
Correct |
462 ms |
19180 KB |
Output is correct |
14 |
Correct |
664 ms |
16876 KB |
Output is correct |
15 |
Correct |
844 ms |
16664 KB |
Output is correct |
16 |
Correct |
466 ms |
12428 KB |
Output is correct |
17 |
Correct |
794 ms |
16784 KB |
Output is correct |
18 |
Correct |
756 ms |
16608 KB |
Output is correct |
19 |
Correct |
858 ms |
20204 KB |
Output is correct |
20 |
Correct |
1405 ms |
10632 KB |
Output is correct |
21 |
Correct |
282 ms |
5868 KB |
Output is correct |
22 |
Correct |
1588 ms |
13428 KB |
Output is correct |
23 |
Correct |
359 ms |
22564 KB |
Output is correct |
24 |
Correct |
855 ms |
16492 KB |
Output is correct |
25 |
Correct |
1592 ms |
23916 KB |
Output is correct |
26 |
Correct |
1258 ms |
24300 KB |
Output is correct |
27 |
Correct |
1216 ms |
23676 KB |
Output is correct |
28 |
Correct |
1014 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1854 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
30 |
Halted |
0 ms |
0 KB |
- |