# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
437373 |
2021-06-26T08:37:49 Z |
Eric_hoo |
Game (IOI13_game) |
C++14 |
|
4413 ms |
59476 KB |
#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define W(x) ((x) ? (x)->w : 0)
#define ID(x, y) (((long long)(x) << 30) + (y))
using namespace std;
inline long long gcd(long long x, long long y) {
while (x && y) {
if (x > y) x = x % y;
else y = y % x;
}
return x | y;
}
struct Node {
long long x; long long y, w; int fix;
int l, r;
Node *lson, *rson;
Node() {fix = rand(), lson = rson = NULL;}
void pushup() {
w = gcd(y, gcd(W(lson), W(rson))), l = r = (x >> 30);
if (lson) l = lson->l;
if (rson) r = rson->r;
}
}NODEPOOL[700000], *NODECUR = NODEPOOL;
typedef pair <Node *, Node *> pnn;
Node *merge(Node *l, Node *r) {
if (!l || !r) return l ? l : r;
if (l->fix > r->fix) {
l->rson = merge(l->rson, r);
l->pushup();
return l;
} else {
r->lson = merge(l, r->lson);
r->pushup();
return r;
}
}
pnn split(Node *T, long long x) {
if (!T) return pnn(NULL, NULL);
if (x < T->x) {
pnn t = split(T->lson, x);
T->lson = t.se, T->pushup();
return mp(t.fi, T);
} else {
pnn t = split(T->rson, x);
T->rson = t.fi, T->pushup();
return mp(T, t.se);
}
}
void Insert(Node *&T, int x, int y, long long w) {
pnn t1 = split(T, ID(y, x - 1)), t2 = split(t1.se, ID(y, x));
if (!t2.fi) t2.fi = NODECUR++;
t2.fi->x = ID(y, x), t2.fi->y = t2.fi->w = w, t2.fi->l = t2.fi->r = y;
T = merge(t1.fi, merge(t2.fi, t2.se));
}
long long Query(Node *T, const int &l, const int &r) {
if (!T || T->l > r || T->r < l) return 0;
if (l <= T->l && T->r <= r) return T->w;
if ((T->x >> 30) < l) return Query(T->rson, l, r);
if ((T->x >> 30) > r) return Query(T->lson, l, r);
return gcd(T->y, gcd(Query(T->lson, l, r), Query(T->rson, l, r)));
}
struct Seg {
Node *T;
Seg *lson, *rson;
Seg() {T = NULL, lson = rson = NULL;}
}SEGPOOL[700000], *SEGCUR = SEGPOOL, *T = NULL;
void Update(Seg *&T, int l, int r, int x, int y, long long w) {
if (!T) T = SEGCUR++;
Insert(T->T, x, y, w);
if (l == r) return ;
int mid = l + r >> 1;
if (x <= mid) Update(T->lson, l, mid, x, y, w);
else Update(T->rson, mid + 1, r, x, y, w);
}
long long Query(Seg *T, int l, int r, int L, int R, int LL, int RR) {
if (!T) return 0;
if (l == L && r == R) return Query(T->T, LL, RR);
int mid = l + r >> 1;
if (R <= mid) return Query(T->lson, l, mid, L, R, LL, RR);
if (L > mid) return Query(T->rson, mid + 1, r, L, R, LL, RR);
return gcd(Query(T->lson, l, mid, L, mid, LL, RR), Query(T->rson, mid + 1, r, mid + 1, R, LL, RR));
}
int N, M, Q;
void read(int &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
void read(long long &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
char st[100];
void print(long long x) {
int tp = 0;
if (!x) st[tp++] = '0';
while (x) st[tp++] = x % 10 + '0', x /= 10;
while (tp--) putchar(st[tp]);
putchar('\n');
}
void init(int R, int C) {
N = R, M = C, srand(2333);
}
void update(int x1, int y1, long long w) {
x1++, y1++;
Update(T, 1, N, x1, y1, w);
}
long long calculate(int x1, int x2, int y1, int y2) {
x1++, x2++, y1++, y2++;
return Query(T, 1, N, x1, y1, x2, y2);
}
Compilation message
game.cpp: In function 'void Update(Seg*&, int, int, int, int, long long int)':
game.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = l + r >> 1;
| ~~^~~
game.cpp: In function 'long long int Query(Seg*, int, int, int, int, int, int)':
game.cpp:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
54980 KB |
Output is correct |
2 |
Correct |
32 ms |
55056 KB |
Output is correct |
3 |
Correct |
36 ms |
54980 KB |
Output is correct |
4 |
Correct |
32 ms |
54956 KB |
Output is correct |
5 |
Correct |
37 ms |
55048 KB |
Output is correct |
6 |
Correct |
34 ms |
54952 KB |
Output is correct |
7 |
Correct |
31 ms |
54984 KB |
Output is correct |
8 |
Correct |
33 ms |
55068 KB |
Output is correct |
9 |
Correct |
33 ms |
54972 KB |
Output is correct |
10 |
Correct |
33 ms |
54980 KB |
Output is correct |
11 |
Correct |
33 ms |
54980 KB |
Output is correct |
12 |
Correct |
33 ms |
55024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
55044 KB |
Output is correct |
2 |
Correct |
39 ms |
54940 KB |
Output is correct |
3 |
Correct |
34 ms |
54988 KB |
Output is correct |
4 |
Correct |
735 ms |
59252 KB |
Output is correct |
5 |
Correct |
322 ms |
59388 KB |
Output is correct |
6 |
Correct |
575 ms |
56092 KB |
Output is correct |
7 |
Correct |
639 ms |
55876 KB |
Output is correct |
8 |
Correct |
409 ms |
56752 KB |
Output is correct |
9 |
Correct |
616 ms |
55948 KB |
Output is correct |
10 |
Correct |
583 ms |
55580 KB |
Output is correct |
11 |
Correct |
31 ms |
55068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
54964 KB |
Output is correct |
2 |
Correct |
35 ms |
55000 KB |
Output is correct |
3 |
Correct |
32 ms |
54988 KB |
Output is correct |
4 |
Correct |
34 ms |
54988 KB |
Output is correct |
5 |
Correct |
33 ms |
54948 KB |
Output is correct |
6 |
Correct |
34 ms |
54996 KB |
Output is correct |
7 |
Correct |
35 ms |
55048 KB |
Output is correct |
8 |
Correct |
33 ms |
54976 KB |
Output is correct |
9 |
Correct |
31 ms |
54980 KB |
Output is correct |
10 |
Correct |
31 ms |
54968 KB |
Output is correct |
11 |
Correct |
33 ms |
54956 KB |
Output is correct |
12 |
Correct |
1016 ms |
59076 KB |
Output is correct |
13 |
Correct |
1872 ms |
55968 KB |
Output is correct |
14 |
Correct |
365 ms |
55528 KB |
Output is correct |
15 |
Correct |
1914 ms |
55824 KB |
Output is correct |
16 |
Correct |
337 ms |
55748 KB |
Output is correct |
17 |
Correct |
759 ms |
56412 KB |
Output is correct |
18 |
Correct |
1602 ms |
56248 KB |
Output is correct |
19 |
Correct |
1279 ms |
56436 KB |
Output is correct |
20 |
Correct |
1175 ms |
55804 KB |
Output is correct |
21 |
Correct |
36 ms |
54988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
54976 KB |
Output is correct |
2 |
Correct |
31 ms |
55040 KB |
Output is correct |
3 |
Correct |
35 ms |
54972 KB |
Output is correct |
4 |
Correct |
33 ms |
55016 KB |
Output is correct |
5 |
Correct |
32 ms |
54984 KB |
Output is correct |
6 |
Correct |
33 ms |
55036 KB |
Output is correct |
7 |
Correct |
32 ms |
54960 KB |
Output is correct |
8 |
Correct |
34 ms |
55060 KB |
Output is correct |
9 |
Correct |
33 ms |
55056 KB |
Output is correct |
10 |
Correct |
33 ms |
54980 KB |
Output is correct |
11 |
Correct |
30 ms |
54988 KB |
Output is correct |
12 |
Correct |
675 ms |
59152 KB |
Output is correct |
13 |
Correct |
325 ms |
59476 KB |
Output is correct |
14 |
Correct |
565 ms |
56116 KB |
Output is correct |
15 |
Correct |
633 ms |
55868 KB |
Output is correct |
16 |
Correct |
404 ms |
56696 KB |
Output is correct |
17 |
Correct |
632 ms |
55876 KB |
Output is correct |
18 |
Correct |
575 ms |
55568 KB |
Output is correct |
19 |
Correct |
1016 ms |
59128 KB |
Output is correct |
20 |
Correct |
1726 ms |
55768 KB |
Output is correct |
21 |
Correct |
369 ms |
55580 KB |
Output is correct |
22 |
Correct |
1909 ms |
55888 KB |
Output is correct |
23 |
Correct |
335 ms |
55728 KB |
Output is correct |
24 |
Correct |
750 ms |
56356 KB |
Output is correct |
25 |
Correct |
1726 ms |
56204 KB |
Output is correct |
26 |
Correct |
1245 ms |
56384 KB |
Output is correct |
27 |
Correct |
1201 ms |
55764 KB |
Output is correct |
28 |
Correct |
501 ms |
55620 KB |
Output is correct |
29 |
Correct |
1552 ms |
58768 KB |
Output is correct |
30 |
Correct |
2537 ms |
55716 KB |
Output is correct |
31 |
Correct |
2287 ms |
55972 KB |
Output is correct |
32 |
Correct |
629 ms |
55644 KB |
Output is correct |
33 |
Correct |
706 ms |
55600 KB |
Output is correct |
34 |
Correct |
386 ms |
55736 KB |
Output is correct |
35 |
Correct |
1008 ms |
56564 KB |
Output is correct |
36 |
Correct |
2370 ms |
56388 KB |
Output is correct |
37 |
Correct |
1780 ms |
56280 KB |
Output is correct |
38 |
Correct |
1759 ms |
55824 KB |
Output is correct |
39 |
Correct |
1503 ms |
56472 KB |
Output is correct |
40 |
Correct |
33 ms |
55040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
54988 KB |
Output is correct |
2 |
Correct |
32 ms |
54988 KB |
Output is correct |
3 |
Correct |
34 ms |
54984 KB |
Output is correct |
4 |
Correct |
34 ms |
54980 KB |
Output is correct |
5 |
Correct |
34 ms |
55000 KB |
Output is correct |
6 |
Correct |
34 ms |
55036 KB |
Output is correct |
7 |
Correct |
35 ms |
55052 KB |
Output is correct |
8 |
Correct |
31 ms |
54988 KB |
Output is correct |
9 |
Correct |
32 ms |
54980 KB |
Output is correct |
10 |
Correct |
33 ms |
55060 KB |
Output is correct |
11 |
Correct |
34 ms |
55076 KB |
Output is correct |
12 |
Correct |
668 ms |
59052 KB |
Output is correct |
13 |
Correct |
359 ms |
59328 KB |
Output is correct |
14 |
Correct |
558 ms |
56260 KB |
Output is correct |
15 |
Correct |
665 ms |
55928 KB |
Output is correct |
16 |
Correct |
405 ms |
56684 KB |
Output is correct |
17 |
Correct |
629 ms |
56112 KB |
Output is correct |
18 |
Correct |
620 ms |
55536 KB |
Output is correct |
19 |
Correct |
1077 ms |
59332 KB |
Output is correct |
20 |
Correct |
1758 ms |
55868 KB |
Output is correct |
21 |
Correct |
366 ms |
55636 KB |
Output is correct |
22 |
Correct |
1876 ms |
55748 KB |
Output is correct |
23 |
Correct |
326 ms |
55816 KB |
Output is correct |
24 |
Correct |
787 ms |
56376 KB |
Output is correct |
25 |
Correct |
1666 ms |
56192 KB |
Output is correct |
26 |
Correct |
1242 ms |
56280 KB |
Output is correct |
27 |
Correct |
1162 ms |
55784 KB |
Output is correct |
28 |
Correct |
501 ms |
55604 KB |
Output is correct |
29 |
Correct |
1528 ms |
58772 KB |
Output is correct |
30 |
Correct |
2660 ms |
55720 KB |
Output is correct |
31 |
Correct |
2236 ms |
55796 KB |
Output is correct |
32 |
Correct |
666 ms |
55592 KB |
Output is correct |
33 |
Correct |
813 ms |
55608 KB |
Output is correct |
34 |
Correct |
400 ms |
55892 KB |
Output is correct |
35 |
Correct |
1135 ms |
56484 KB |
Output is correct |
36 |
Correct |
2562 ms |
56212 KB |
Output is correct |
37 |
Correct |
1765 ms |
56216 KB |
Output is correct |
38 |
Correct |
1771 ms |
55820 KB |
Output is correct |
39 |
Correct |
790 ms |
55648 KB |
Output is correct |
40 |
Correct |
2589 ms |
57668 KB |
Output is correct |
41 |
Correct |
4413 ms |
55732 KB |
Output is correct |
42 |
Correct |
3882 ms |
55576 KB |
Output is correct |
43 |
Correct |
749 ms |
55704 KB |
Output is correct |
44 |
Correct |
1140 ms |
55492 KB |
Output is correct |
45 |
Correct |
1319 ms |
56428 KB |
Output is correct |
46 |
Correct |
3309 ms |
56256 KB |
Output is correct |
47 |
Correct |
3339 ms |
56048 KB |
Output is correct |
48 |
Correct |
2976 ms |
55620 KB |
Output is correct |
49 |
Correct |
37 ms |
54980 KB |
Output is correct |