# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
99201 |
2019-03-01T16:01:11 Z |
maruii |
Game (IOI13_game) |
C++14 |
|
6361 ms |
257024 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int R, C;
long long gcd2(long long X, long long Y) {
if(!X) return Y;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct ST{
struct Node{
int l=0, r=0;
ll v=0;
};
ll v;
int x, s, e;
vector<Node> node;
void update(int nn, int ns, int ne){
if(ns>x || ne<x) return;
if(ns==ne){
node[nn].v = v;
return;
}
int m = ns+ne>>1;
if(m<x){
if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1);
update(node[nn].r, m+1, ne);
}
else{
if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1);
update(node[nn].l, ns, m);
}
node[nn].v = gcd2(node[nn].l?node[node[nn].l].v:0ll, node[nn].r?node[node[nn].r].v:0ll);
}
void update(int a, ll b){
tie(x, v) = tie(a, b);
update(0, 0, C);
}
ll query(int nn, int ns, int ne){
if(ns>e || ne<s) return 0;
if(s<=ns && ne<=e) return node[nn].v;
int m = ns+ne>>1;
return gcd2(node[nn].l?query(node[nn].l, ns, m):0ll, node[nn].r?query(node[nn].r, m+1, ne):0ll);
}
ll query(int a, int b){
tie(s, e) = tie(a, b);
return query(0, 0, C);
}
};
struct ST2{
struct Node{
int l=0, r=0;
ST v;
};
ll v;
int x, xx, s, e, ss, ee;
vector<Node> node;
void update(int nn, int ns, int ne){
if(ns>x || ne<x) return;
if(ns==ne){
node[nn].v.update(xx, v);
return;
}
int m = ns+ne>>1;
if(m<x){
if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1), node[node[nn].r].v.node.resize(1);
update(node[nn].r, m+1, ne);
}
else{
if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1), node[node[nn].l].v.node.resize(1);
update(node[nn].l, ns, m);
}
node[nn].v.update(xx, gcd2(node[nn].l?node[node[nn].l].v.query(xx, xx):0ll, node[nn].r?node[node[nn].r].v.query(xx, xx):0ll));
}
void update(int a, int b, ll c){
tie(x, xx, v) = tie(a, b, c);
update(0, 0, R);
}
ll query(int nn, int ns, int ne){
if(ns>e || ne<s) return 0;
if(s<=ns && ne<=e) return node[nn].v.query(ss, ee);
int m = ns+ne>>1;
return gcd2(node[nn].l?query(node[nn].l, ns, m):0ll, node[nn].r?query(node[nn].r, m+1, ne):0ll);
}
ll query(int a, int b, int c, int d){
tie(s, e, ss, ee) = tie(a, b, c, d);
return query(0, 0, R);
}
} seg;
void init(int R_, int C_) {
R = R_ - 1, C = C_ - 1;
seg.node.resize(1);
seg.node[0].v.node.resize(1);
}
void update(int P, int Q, ll K) {
seg.update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return seg.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 member function 'void ST::update(int, int, int)':
game.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
game.cpp: In member function 'll ST::query(int, int, int)':
game.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
game.cpp: In member function 'void ST2::update(int, int, int)':
game.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
game.cpp: In member function 'll ST2::query(int, int, int)':
game.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
795 ms |
11036 KB |
Output is correct |
5 |
Correct |
689 ms |
11612 KB |
Output is correct |
6 |
Correct |
852 ms |
8024 KB |
Output is correct |
7 |
Correct |
1010 ms |
7940 KB |
Output is correct |
8 |
Correct |
552 ms |
6352 KB |
Output is correct |
9 |
Correct |
869 ms |
8240 KB |
Output is correct |
10 |
Correct |
787 ms |
7388 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
1341 ms |
14060 KB |
Output is correct |
13 |
Correct |
2760 ms |
5976 KB |
Output is correct |
14 |
Correct |
510 ms |
2480 KB |
Output is correct |
15 |
Correct |
3377 ms |
7796 KB |
Output is correct |
16 |
Correct |
342 ms |
14840 KB |
Output is correct |
17 |
Correct |
1555 ms |
10388 KB |
Output is correct |
18 |
Correct |
2602 ms |
15396 KB |
Output is correct |
19 |
Correct |
2178 ms |
14952 KB |
Output is correct |
20 |
Correct |
2222 ms |
14200 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
10 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
844 ms |
11180 KB |
Output is correct |
13 |
Correct |
582 ms |
11488 KB |
Output is correct |
14 |
Correct |
889 ms |
7956 KB |
Output is correct |
15 |
Correct |
932 ms |
8028 KB |
Output is correct |
16 |
Correct |
656 ms |
6292 KB |
Output is correct |
17 |
Correct |
845 ms |
8316 KB |
Output is correct |
18 |
Correct |
792 ms |
7404 KB |
Output is correct |
19 |
Correct |
1301 ms |
13996 KB |
Output is correct |
20 |
Correct |
2832 ms |
6208 KB |
Output is correct |
21 |
Correct |
365 ms |
2280 KB |
Output is correct |
22 |
Correct |
3425 ms |
7948 KB |
Output is correct |
23 |
Correct |
364 ms |
15000 KB |
Output is correct |
24 |
Correct |
1592 ms |
10224 KB |
Output is correct |
25 |
Correct |
2768 ms |
15312 KB |
Output is correct |
26 |
Correct |
2443 ms |
14904 KB |
Output is correct |
27 |
Correct |
2156 ms |
14240 KB |
Output is correct |
28 |
Correct |
1467 ms |
151780 KB |
Output is correct |
29 |
Correct |
3007 ms |
167416 KB |
Output is correct |
30 |
Correct |
6361 ms |
120660 KB |
Output is correct |
31 |
Correct |
5844 ms |
97436 KB |
Output is correct |
32 |
Correct |
772 ms |
1804 KB |
Output is correct |
33 |
Correct |
1168 ms |
4412 KB |
Output is correct |
34 |
Correct |
1115 ms |
164904 KB |
Output is correct |
35 |
Correct |
2481 ms |
84200 KB |
Output is correct |
36 |
Correct |
4565 ms |
164876 KB |
Output is correct |
37 |
Correct |
4026 ms |
165128 KB |
Output is correct |
38 |
Correct |
3891 ms |
164536 KB |
Output is correct |
39 |
Correct |
3308 ms |
129800 KB |
Output is correct |
40 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
256 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
863 ms |
10820 KB |
Output is correct |
13 |
Correct |
497 ms |
11352 KB |
Output is correct |
14 |
Correct |
860 ms |
7844 KB |
Output is correct |
15 |
Correct |
984 ms |
7772 KB |
Output is correct |
16 |
Correct |
604 ms |
6056 KB |
Output is correct |
17 |
Correct |
972 ms |
7956 KB |
Output is correct |
18 |
Correct |
865 ms |
7184 KB |
Output is correct |
19 |
Correct |
1353 ms |
13804 KB |
Output is correct |
20 |
Correct |
2896 ms |
5828 KB |
Output is correct |
21 |
Correct |
412 ms |
2040 KB |
Output is correct |
22 |
Correct |
3209 ms |
7692 KB |
Output is correct |
23 |
Correct |
370 ms |
14684 KB |
Output is correct |
24 |
Correct |
1584 ms |
10064 KB |
Output is correct |
25 |
Correct |
2680 ms |
15248 KB |
Output is correct |
26 |
Correct |
2366 ms |
14840 KB |
Output is correct |
27 |
Correct |
2166 ms |
14020 KB |
Output is correct |
28 |
Correct |
1384 ms |
151388 KB |
Output is correct |
29 |
Correct |
2743 ms |
167184 KB |
Output is correct |
30 |
Correct |
6264 ms |
120344 KB |
Output is correct |
31 |
Correct |
5441 ms |
97024 KB |
Output is correct |
32 |
Correct |
633 ms |
1656 KB |
Output is correct |
33 |
Correct |
920 ms |
4124 KB |
Output is correct |
34 |
Correct |
919 ms |
164480 KB |
Output is correct |
35 |
Correct |
2699 ms |
84184 KB |
Output is correct |
36 |
Correct |
4450 ms |
164880 KB |
Output is correct |
37 |
Correct |
3820 ms |
164692 KB |
Output is correct |
38 |
Correct |
3882 ms |
164300 KB |
Output is correct |
39 |
Runtime error |
1915 ms |
257024 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
40 |
Halted |
0 ms |
0 KB |
- |