# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
437275 |
2021-06-26T06:32:48 Z |
Mackerel_Pike |
Game (IOI13_game) |
C++14 |
|
4953 ms |
256000 KB |
#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
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;
}
class SegmentTree{
public:
static const int maxv = 1e7 + 5;
static const int siz = 1000000000;
int tot, r;
int ls[maxv], rs[maxv], rt[maxv];
ll dat[maxv];
inline void init(){ r = 0, tot = 1; return; }
inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
if(!u)
u = tot++, dat[u] = 0;
//printf("update2 u = %d l = %d r = %d\n", u, l, r);
if(l == r){
dat[u] = k;
return;
}
int md = l + r >> 1;
if(q <= md)
update2(q, k, ls[u], l, md);
else
update2(q, k, rs[u], md + 1, r);
dat[u] = gcd2(dat[ls[u]], dat[rs[u]]);
return;
}
inline void pushUp(int q, int &v, int vl, int vr, int l = 0, int r = siz - 1){
if(!v)
v = tot++, dat[v] = 0;
if(l == r){
dat[v] = gcd2(dat[vl], dat[vr]);
return;
}
int md = l + r >> 1;
if(q <= md)
pushUp(q, ls[v], ls[vl], ls[vr], l, md);
else
pushUp(q, rs[v], rs[vl], rs[vr], md + 1, r);
dat[v] = gcd2(dat[ls[v]], dat[rs[v]]);
return;
}
inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
if(!u)
u = tot++, dat[u] = 0;
//printf("update u = %d rt = %d\n", u, rt[u]);
if(l == r){
update2(q, k, rt[u]);
return;
}
int md = l + r >> 1;
if(p <= md)
update(p, q, k, ls[u], l, md);
else
update(p, q, k, rs[u], md + 1, r);
pushUp(q, rt[u], rt[ls[u]], rt[rs[u]]);
return;
}
inline ll query2(int s, int t, int u, int l = 0, int r = siz - 1){
//printf("query2 u = %d\n", u);
if(!u){
return 0;
}
if(l >= s && r <= t){
return dat[u];
}
int md = l + r >> 1;
if(s > md)
return query2(s, t, rs[u], md + 1, r);
if(t <= md)
return query2(s, t, ls[u], l, md);
return gcd2(query2(s, t, ls[u], l, md), query2(s, t, rs[u], md + 1, r));
}
inline ll query(int p, int q, int s, int t, int u, int l = 0, int r = siz - 1){
if(!u)
return 0;
if(l >= p && r <= q)
return query2(s, t, rt[u]);
int md = l + r >> 1;
if(p > md)
return query(p, q, s, t, rs[u], md + 1, r);
if(q <= md)
return query(p, q, s, t, ls[u], l, md);
return gcd2(query(p, q, s, t, rs[u], md + 1, r), query(p, q, s, t, ls[u], l, md));
}
} seg;
void init(int R, int C) {
seg.init();
}
void update(int P, int Q, long long K) {
seg.update(P, Q, K, seg.r);
return;
}
long long calculate(int P, int Q, int U, int V) {
return seg.query(P, U, Q, V, seg.r);
}
Compilation message
game.cpp: In member function 'void SegmentTree::update2(int, ll, int&, int, int)':
game.cpp:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int md = l + r >> 1;
| ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, int&, int, int, int, int)':
game.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int md = l + r >> 1;
| ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:65:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int md = l + r >> 1;
| ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:82:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int md = l + r >> 1;
| ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int md = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
552 KB |
Output is correct |
3 |
Correct |
2 ms |
556 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
759 ms |
31656 KB |
Output is correct |
5 |
Correct |
604 ms |
31520 KB |
Output is correct |
6 |
Correct |
868 ms |
29180 KB |
Output is correct |
7 |
Correct |
963 ms |
28808 KB |
Output is correct |
8 |
Correct |
475 ms |
19536 KB |
Output is correct |
9 |
Correct |
801 ms |
29044 KB |
Output is correct |
10 |
Correct |
802 ms |
28512 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
552 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
970 ms |
16644 KB |
Output is correct |
13 |
Correct |
1385 ms |
9776 KB |
Output is correct |
14 |
Correct |
419 ms |
5828 KB |
Output is correct |
15 |
Correct |
1653 ms |
13236 KB |
Output is correct |
16 |
Correct |
462 ms |
18692 KB |
Output is correct |
17 |
Correct |
934 ms |
15592 KB |
Output is correct |
18 |
Correct |
1706 ms |
20068 KB |
Output is correct |
19 |
Correct |
1428 ms |
20164 KB |
Output is correct |
20 |
Correct |
1403 ms |
19780 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
767 ms |
31716 KB |
Output is correct |
13 |
Correct |
514 ms |
31492 KB |
Output is correct |
14 |
Correct |
725 ms |
29056 KB |
Output is correct |
15 |
Correct |
759 ms |
28840 KB |
Output is correct |
16 |
Correct |
455 ms |
19560 KB |
Output is correct |
17 |
Correct |
806 ms |
28976 KB |
Output is correct |
18 |
Correct |
722 ms |
28500 KB |
Output is correct |
19 |
Correct |
1000 ms |
16580 KB |
Output is correct |
20 |
Correct |
1342 ms |
9872 KB |
Output is correct |
21 |
Correct |
415 ms |
5680 KB |
Output is correct |
22 |
Correct |
1580 ms |
13204 KB |
Output is correct |
23 |
Correct |
505 ms |
18708 KB |
Output is correct |
24 |
Correct |
939 ms |
15568 KB |
Output is correct |
25 |
Correct |
1694 ms |
20068 KB |
Output is correct |
26 |
Correct |
1378 ms |
20240 KB |
Output is correct |
27 |
Correct |
1410 ms |
19740 KB |
Output is correct |
28 |
Correct |
857 ms |
168048 KB |
Output is correct |
29 |
Correct |
2182 ms |
185816 KB |
Output is correct |
30 |
Correct |
4718 ms |
126540 KB |
Output is correct |
31 |
Correct |
4433 ms |
98264 KB |
Output is correct |
32 |
Correct |
443 ms |
10280 KB |
Output is correct |
33 |
Correct |
633 ms |
11896 KB |
Output is correct |
34 |
Correct |
492 ms |
179616 KB |
Output is correct |
35 |
Correct |
1547 ms |
97732 KB |
Output is correct |
36 |
Correct |
3387 ms |
183852 KB |
Output is correct |
37 |
Correct |
2430 ms |
183812 KB |
Output is correct |
38 |
Correct |
2676 ms |
183328 KB |
Output is correct |
39 |
Correct |
2015 ms |
143332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
4 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
758 ms |
31656 KB |
Output is correct |
13 |
Correct |
530 ms |
31468 KB |
Output is correct |
14 |
Correct |
866 ms |
29044 KB |
Output is correct |
15 |
Correct |
872 ms |
28768 KB |
Output is correct |
16 |
Correct |
518 ms |
19604 KB |
Output is correct |
17 |
Correct |
751 ms |
28960 KB |
Output is correct |
18 |
Correct |
775 ms |
28556 KB |
Output is correct |
19 |
Correct |
1049 ms |
16732 KB |
Output is correct |
20 |
Correct |
1376 ms |
9896 KB |
Output is correct |
21 |
Correct |
405 ms |
5752 KB |
Output is correct |
22 |
Correct |
1574 ms |
13144 KB |
Output is correct |
23 |
Correct |
420 ms |
18628 KB |
Output is correct |
24 |
Correct |
1025 ms |
15552 KB |
Output is correct |
25 |
Correct |
1644 ms |
20084 KB |
Output is correct |
26 |
Correct |
1417 ms |
20128 KB |
Output is correct |
27 |
Correct |
1436 ms |
19560 KB |
Output is correct |
28 |
Correct |
839 ms |
168044 KB |
Output is correct |
29 |
Correct |
2199 ms |
185884 KB |
Output is correct |
30 |
Correct |
4953 ms |
126628 KB |
Output is correct |
31 |
Correct |
4526 ms |
98284 KB |
Output is correct |
32 |
Correct |
453 ms |
10328 KB |
Output is correct |
33 |
Correct |
663 ms |
11860 KB |
Output is correct |
34 |
Correct |
536 ms |
179524 KB |
Output is correct |
35 |
Correct |
1530 ms |
97796 KB |
Output is correct |
36 |
Correct |
3356 ms |
183788 KB |
Output is correct |
37 |
Correct |
2522 ms |
183804 KB |
Output is correct |
38 |
Correct |
2623 ms |
183352 KB |
Output is correct |
39 |
Runtime error |
842 ms |
256000 KB |
Execution killed with signal 11 |
40 |
Halted |
0 ms |
0 KB |
- |