oj.uz

Submission #437359

# Submission time Handle Problem Language Result Execution time Memory
437359 2021-06-26T08:15:27 Z Eric_hoo Game (IOI13_game) C++14
100 / 100
 10013 ms 54496 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;
	Node *lson, *rson;
	Node() {fix = rand(), lson = rson = NULL;}
	void pushup() {w = gcd(y, gcd(W(lson), W(rson)));}
}NODEPOOL[700000], *NODECUR = NODEPOOL;

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;
	}
}

void split(Node *T, long long x, Node *&l, Node *&r) {
	if (!T) {l = r = NULL; return ;}
	if (x < T->x) split(T->lson, x, l, r), T->lson = r, T->pushup(), r = T;
	else split(T->rson, x, l, r), T->rson = l, T->pushup(), l = T;
}

void Insert(Node *&T, int x, int y, long long w) {
	Node *t1, *t2, *t3;
	split(T, ID(y, x - 1), t1, t2), split(t2, ID(y, x), t2, t3);
	if (!t2) t2 = NODECUR++;
	t2->x = ID(y, x), t2->y = t2->w = w;
	T = merge(t1, merge(t2, t3));
}

long long Query(Node *T, int l, int r) {
	Node *t1, *t2, *t3;
	split(T, ID(l, -1), t1, t2), split(t2, ID(r + 1, -1), t2, t3);
	long long ans = W(t2);
	T = merge(t1, merge(t2, t3));
	return ans;
}

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:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid = l + r >> 1;
      |            ~~^~~
game.cpp: In function 'long long int Query(Seg*, int, int, int, int, int, int)':
game.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49468 KB Output is correct
2 Correct 34 ms 49540 KB Output is correct
3 Correct 28 ms 49584 KB Output is correct
4 Correct 28 ms 49556 KB Output is correct
5 Correct 28 ms 49512 KB Output is correct
6 Correct 29 ms 49664 KB Output is correct
7 Correct 28 ms 49612 KB Output is correct
8 Correct 27 ms 49572 KB Output is correct
9 Correct 27 ms 49572 KB Output is correct
10 Correct 28 ms 49560 KB Output is correct
11 Correct 31 ms 49544 KB Output is correct
12 Correct 29 ms 49580 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49588 KB Output is correct
2 Correct 28 ms 49504 KB Output is correct
3 Correct 29 ms 49580 KB Output is correct
4 Correct 1180 ms 53648 KB Output is correct
5 Correct 512 ms 53912 KB Output is correct
6 Correct 1268 ms 50616 KB Output is correct
7 Correct 1453 ms 50320 KB Output is correct
8 Correct 987 ms 51292 KB Output is correct
9 Correct 1446 ms 50472 KB Output is correct
10 Correct 1246 ms 50252 KB Output is correct
11 Correct 35 ms 49488 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49476 KB Output is correct
2 Correct 30 ms 49604 KB Output is correct
3 Correct 31 ms 49484 KB Output is correct
4 Correct 29 ms 49524 KB Output is correct
5 Correct 28 ms 49476 KB Output is correct
6 Correct 28 ms 49596 KB Output is correct
7 Correct 28 ms 49524 KB Output is correct
8 Correct 34 ms 49472 KB Output is correct
9 Correct 30 ms 49576 KB Output is correct
10 Correct 28 ms 49492 KB Output is correct
11 Correct 28 ms 49528 KB Output is correct
12 Correct 1776 ms 53664 KB Output is correct
13 Correct 3990 ms 50288 KB Output is correct
14 Correct 654 ms 50020 KB Output is correct
15 Correct 4462 ms 50300 KB Output is correct
16 Correct 518 ms 50244 KB Output is correct
17 Correct 1986 ms 50892 KB Output is correct
18 Correct 3633 ms 50528 KB Output is correct
19 Correct 2990 ms 50684 KB Output is correct
20 Correct 2764 ms 50268 KB Output is correct
21 Correct 28 ms 49476 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49648 KB Output is correct
2 Correct 28 ms 49524 KB Output is correct
3 Correct 30 ms 49552 KB Output is correct
4 Correct 28 ms 49496 KB Output is correct
5 Correct 29 ms 49600 KB Output is correct
6 Correct 28 ms 49504 KB Output is correct
7 Correct 27 ms 49576 KB Output is correct
8 Correct 30 ms 49476 KB Output is correct
9 Correct 28 ms 49480 KB Output is correct
10 Correct 29 ms 49476 KB Output is correct
11 Correct 28 ms 49476 KB Output is correct
12 Correct 1190 ms 53524 KB Output is correct
13 Correct 485 ms 53956 KB Output is correct
14 Correct 1238 ms 50648 KB Output is correct
15 Correct 1424 ms 50408 KB Output is correct
16 Correct 953 ms 51128 KB Output is correct
17 Correct 1356 ms 50464 KB Output is correct
18 Correct 1230 ms 49996 KB Output is correct
19 Correct 1762 ms 53580 KB Output is correct
20 Correct 4002 ms 50504 KB Output is correct
21 Correct 667 ms 50108 KB Output is correct
22 Correct 4290 ms 50328 KB Output is correct
23 Correct 497 ms 50556 KB Output is correct
24 Correct 1951 ms 50888 KB Output is correct
25 Correct 3561 ms 50760 KB Output is correct
26 Correct 2853 ms 50788 KB Output is correct
27 Correct 2734 ms 50304 KB Output is correct
28 Correct 1088 ms 50100 KB Output is correct
29 Correct 2327 ms 53344 KB Output is correct
30 Correct 5712 ms 50372 KB Output is correct
31 Correct 5105 ms 50640 KB Output is correct
32 Correct 873 ms 50064 KB Output is correct
33 Correct 1263 ms 50212 KB Output is correct
34 Correct 560 ms 50220 KB Output is correct
35 Correct 2285 ms 51012 KB Output is correct
36 Correct 4511 ms 50708 KB Output is correct
37 Correct 3615 ms 50708 KB Output is correct
38 Correct 3544 ms 50156 KB Output is correct
39 Correct 2925 ms 51276 KB Output is correct
40 Correct 40 ms 49552 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49472 KB Output is correct
2 Correct 33 ms 49484 KB Output is correct
3 Correct 35 ms 49540 KB Output is correct
4 Correct 32 ms 49472 KB Output is correct
5 Correct 33 ms 49592 KB Output is correct
6 Correct 31 ms 49488 KB Output is correct
7 Correct 32 ms 49484 KB Output is correct
8 Correct 33 ms 49488 KB Output is correct
9 Correct 34 ms 49476 KB Output is correct
10 Correct 33 ms 49604 KB Output is correct
11 Correct 32 ms 49600 KB Output is correct
12 Correct 1196 ms 54212 KB Output is correct
13 Correct 532 ms 54496 KB Output is correct
14 Correct 1265 ms 51140 KB Output is correct
15 Correct 1439 ms 50980 KB Output is correct
16 Correct 953 ms 51840 KB Output is correct
17 Correct 1399 ms 51000 KB Output is correct
18 Correct 1295 ms 50668 KB Output is correct
19 Correct 1840 ms 54236 KB Output is correct
20 Correct 3971 ms 50852 KB Output is correct
21 Correct 647 ms 50628 KB Output is correct
22 Correct 4335 ms 50816 KB Output is correct
23 Correct 519 ms 51016 KB Output is correct
24 Correct 1937 ms 51432 KB Output is correct
25 Correct 3495 ms 51192 KB Output is correct
26 Correct 2837 ms 51368 KB Output is correct
27 Correct 2681 ms 50780 KB Output is correct
28 Correct 1203 ms 50708 KB Output is correct
29 Correct 2495 ms 53772 KB Output is correct
30 Correct 6201 ms 50600 KB Output is correct
31 Correct 5472 ms 51248 KB Output is correct
32 Correct 850 ms 50536 KB Output is correct
33 Correct 1249 ms 50604 KB Output is correct
34 Correct 564 ms 51012 KB Output is correct
35 Correct 2275 ms 51256 KB Output is correct
36 Correct 4641 ms 51256 KB Output is correct
37 Correct 3576 ms 51312 KB Output is correct
38 Correct 3537 ms 50784 KB Output is correct
39 Correct 1627 ms 50600 KB Output is correct
40 Correct 4204 ms 52788 KB Output is correct
41 Correct 10013 ms 50760 KB Output is correct
42 Correct 8738 ms 50772 KB Output is correct
43 Correct 867 ms 50784 KB Output is correct
44 Correct 1478 ms 50836 KB Output is correct
45 Correct 3039 ms 51436 KB Output is correct
46 Correct 6167 ms 51068 KB Output is correct
47 Correct 6182 ms 51276 KB Output is correct
48 Correct 5775 ms 50592 KB Output is correct
49 Correct 33 ms 49612 KB Output is correct