oj.uz

Submission #437373

# Submission time Handle Problem Language Result Execution time Memory
437373 2021-06-26T08:37:49 Z Eric_hoo Game (IOI13_game) C++14
100 / 100
 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;
      |            ~~^~~

Subtask #1
10.0 / 10.0

# 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

Subtask #2
27.0 / 27.0

# 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

Subtask #3
26.0 / 26.0

# 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

Subtask #4
17.0 / 17.0

# 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

Subtask #5
20.0 / 20.0

# 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