oj.uz

Submission #437334

# Submission time Handle Problem Language Result Execution time Memory
437334 2021-06-26T07:40:35 Z Eric_hoo Game (IOI13_game) C++14
100 / 100
 9113 ms 53952 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;

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;
	T = merge(t1.fi, merge(t2.fi, t2.se));
}

long long Query(Node *T, int l, int r) {
	pnn t1 = split(T, ID(l, -1)), t2 = split(t1.se, ID(r + 1, -1));
	long long ans = W(t2.fi);
	T = merge(t1.fi, merge(t2.fi, t2.se));
	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:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid = l + r >> 1;
      |            ~~^~~
game.cpp: In function 'long long int Query(Seg*, int, int, int, int, int, int)':
game.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49612 KB Output is correct
2 Correct 30 ms 49512 KB Output is correct
3 Correct 29 ms 49556 KB Output is correct
4 Correct 28 ms 49516 KB Output is correct
5 Correct 28 ms 49612 KB Output is correct
6 Correct 28 ms 49576 KB Output is correct
7 Correct 29 ms 49484 KB Output is correct
8 Correct 27 ms 49484 KB Output is correct
9 Correct 28 ms 49612 KB Output is correct
10 Correct 27 ms 49504 KB Output is correct
11 Correct 33 ms 49564 KB Output is correct
12 Correct 34 ms 49584 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49476 KB Output is correct
2 Correct 27 ms 49544 KB Output is correct
3 Correct 31 ms 49496 KB Output is correct
4 Correct 1146 ms 53580 KB Output is correct
5 Correct 513 ms 53912 KB Output is correct
6 Correct 1272 ms 50704 KB Output is correct
7 Correct 1441 ms 50340 KB Output is correct
8 Correct 937 ms 51352 KB Output is correct
9 Correct 1395 ms 50500 KB Output is correct
10 Correct 1231 ms 49984 KB Output is correct
11 Correct 29 ms 49512 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49680 KB Output is correct
2 Correct 33 ms 49572 KB Output is correct
3 Correct 30 ms 49544 KB Output is correct
4 Correct 28 ms 49528 KB Output is correct
5 Correct 28 ms 49484 KB Output is correct
6 Correct 28 ms 49564 KB Output is correct
7 Correct 29 ms 49568 KB Output is correct
8 Correct 29 ms 49532 KB Output is correct
9 Correct 32 ms 49600 KB Output is correct
10 Correct 30 ms 49532 KB Output is correct
11 Correct 35 ms 49612 KB Output is correct
12 Correct 1847 ms 53612 KB Output is correct
13 Correct 3968 ms 50532 KB Output is correct
14 Correct 654 ms 50140 KB Output is correct
15 Correct 4356 ms 50292 KB Output is correct
16 Correct 529 ms 50224 KB Output is correct
17 Correct 2206 ms 50952 KB Output is correct
18 Correct 4505 ms 50524 KB Output is correct
19 Correct 3305 ms 50776 KB Output is correct
20 Correct 2815 ms 50192 KB Output is correct
21 Correct 32 ms 49596 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49564 KB Output is correct
2 Correct 31 ms 49512 KB Output is correct
3 Correct 31 ms 49536 KB Output is correct
4 Correct 31 ms 49512 KB Output is correct
5 Correct 28 ms 49508 KB Output is correct
6 Correct 29 ms 49552 KB Output is correct
7 Correct 33 ms 49560 KB Output is correct
8 Correct 31 ms 49580 KB Output is correct
9 Correct 28 ms 49604 KB Output is correct
10 Correct 45 ms 49504 KB Output is correct
11 Correct 29 ms 49544 KB Output is correct
12 Correct 1159 ms 53716 KB Output is correct
13 Correct 474 ms 53952 KB Output is correct
14 Correct 1222 ms 50752 KB Output is correct
15 Correct 1437 ms 50372 KB Output is correct
16 Correct 968 ms 51104 KB Output is correct
17 Correct 1348 ms 50456 KB Output is correct
18 Correct 1269 ms 50276 KB Output is correct
19 Correct 1755 ms 53560 KB Output is correct
20 Correct 3956 ms 50612 KB Output is correct
21 Correct 647 ms 50172 KB Output is correct
22 Correct 4464 ms 50532 KB Output is correct
23 Correct 523 ms 50288 KB Output is correct
24 Correct 1992 ms 50972 KB Output is correct
25 Correct 3616 ms 50816 KB Output is correct
26 Correct 2877 ms 50676 KB Output is correct
27 Correct 2718 ms 50204 KB Output is correct
28 Correct 1158 ms 50112 KB Output is correct
29 Correct 2592 ms 53228 KB Output is correct
30 Correct 6282 ms 50164 KB Output is correct
31 Correct 5174 ms 50328 KB Output is correct
32 Correct 871 ms 50244 KB Output is correct
33 Correct 1247 ms 50100 KB Output is correct
34 Correct 625 ms 50340 KB Output is correct
35 Correct 2275 ms 50984 KB Output is correct
36 Correct 4657 ms 50624 KB Output is correct
37 Correct 3530 ms 50720 KB Output is correct
38 Correct 3703 ms 50220 KB Output is correct
39 Correct 3451 ms 50796 KB Output is correct
40 Correct 31 ms 49496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 49516 KB Output is correct
2 Correct 29 ms 49548 KB Output is correct
3 Correct 29 ms 49468 KB Output is correct
4 Correct 38 ms 49548 KB Output is correct
5 Correct 27 ms 49576 KB Output is correct
6 Correct 27 ms 49584 KB Output is correct
7 Correct 27 ms 49564 KB Output is correct
8 Correct 30 ms 49508 KB Output is correct
9 Correct 30 ms 49524 KB Output is correct
10 Correct 30 ms 49484 KB Output is correct
11 Correct 28 ms 49484 KB Output is correct
12 Correct 1215 ms 53548 KB Output is correct
13 Correct 567 ms 53948 KB Output is correct
14 Correct 1363 ms 50584 KB Output is correct
15 Correct 1451 ms 50400 KB Output is correct
16 Correct 977 ms 51148 KB Output is correct
17 Correct 1563 ms 50456 KB Output is correct
18 Correct 1232 ms 50008 KB Output is correct
19 Correct 1744 ms 53588 KB Output is correct
20 Correct 3974 ms 50256 KB Output is correct
21 Correct 661 ms 50044 KB Output is correct
22 Correct 4588 ms 50296 KB Output is correct
23 Correct 540 ms 50248 KB Output is correct
24 Correct 2158 ms 50852 KB Output is correct
25 Correct 3767 ms 50636 KB Output is correct
26 Correct 2939 ms 50660 KB Output is correct
27 Correct 2698 ms 50132 KB Output is correct
28 Correct 1109 ms 50136 KB Output is correct
29 Correct 2404 ms 53340 KB Output is correct
30 Correct 5736 ms 50080 KB Output is correct
31 Correct 5208 ms 50292 KB Output is correct
32 Correct 839 ms 50116 KB Output is correct
33 Correct 1263 ms 50148 KB Output is correct
34 Correct 565 ms 50548 KB Output is correct
35 Correct 2248 ms 51008 KB Output is correct
36 Correct 4934 ms 50564 KB Output is correct
37 Correct 3611 ms 50728 KB Output is correct
38 Correct 3539 ms 50452 KB Output is correct
39 Correct 1635 ms 50160 KB Output is correct
40 Correct 3938 ms 52208 KB Output is correct
41 Correct 9113 ms 50096 KB Output is correct
42 Correct 8177 ms 50008 KB Output is correct
43 Correct 867 ms 50260 KB Output is correct
44 Correct 1553 ms 50100 KB Output is correct
45 Correct 2922 ms 50720 KB Output is correct
46 Correct 5693 ms 50460 KB Output is correct
47 Correct 5877 ms 50568 KB Output is correct
48 Correct 5398 ms 50056 KB Output is correct
49 Correct 36 ms 49476 KB Output is correct