oj.uz

Submission #855482

# Submission time Handle Problem Language Result Execution time Memory
855482 2023-10-01T10:20:51 Z SanguineChameleon Game (IOI13_game) C++17
100 / 100
 6289 ms 67804 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 gen(69420);

struct node_y {
	unsigned long long w;
	pair<int, int> pos;
	long long val;
	node_y *lch;
	node_y *rch;
	int sz;
	long long g;

	node_y(pair<int, int> _pos, long long _val): w(gen()), pos(_pos), val(_val), lch(nullptr), rch(nullptr), sz(1), g(val) {};
};

void fix(node_y *u) {
	u->sz = 1;
	u->g = u->val;
	for (auto v: {u->lch, u->rch}) {
		if (v) {
			u->sz += v->sz;
			u->g = __gcd(u->g, v->g);
		}
	}
}

node_y* merge(node_y *lu, node_y *ru) {
	if (!lu) {
		return ru;
	}
	if (!ru) {
		return lu;
	}
	if (lu->w > ru->w) {
		lu->rch = merge(lu->rch, ru);
		fix(lu);
		return lu;
	}
	else {
		ru->lch = merge(lu, ru->lch);
		fix(ru);
		return ru;
	}
}

pair<node_y*, node_y*> split(node_y *u, pair<int, int> pos) {
	if (!u) {
		return {nullptr, nullptr};
	}
	if (u->pos <= pos) {
		auto parts = split(u->rch, pos);
		u->rch = parts.first;
		fix(u);
		return {u, parts.second};
	}
	else {
		auto parts = split(u->lch, pos);
		u->lch = parts.second;
		fix(u);
		return {parts.first, u};
	}
}

void update_y(node_y *&root_y, int x, int y, long long val) {
	node_y *part1, *part2, *part3;
	tie(part1, part2) = split(root_y, {y, x - 1});
	tie(part2, part3) = split(part2, {y, x});
	root_y = merge(merge(part1, new node_y({y, x}, val)), part3);
}

long long get_y(node_y *&root_y, int ly, int ry) {
	node_y *part1, *part2, *part3;
	tie(part1, part2) = split(root_y, {ly, -1});
	tie(part2, part3) = split(part2, {ry + 1, -1});
	long long res = (part2 ? part2->g : 0);
	root_y = merge(merge(part1, part2), part3);
	return res;
}

struct node_x {
	node_y *root_y;
	node_x *lch;
	node_x *rch;

	node_x(): root_y(nullptr), lch(nullptr), rch(nullptr) {};
};

void update_x(node_x *&u, int lt, int rt, int x, int y, long long val) {
	if (!u) {
		u = new node_x();
	}
	update_y(u->root_y, x, y, val);
	if (lt == rt) {
		return;
	}
	int mt = (lt + rt) >> 1;
	if (x <= mt) {
		update_x(u->lch, lt, mt, x, y, val);
	}
	else {
		update_x(u->rch, mt + 1, rt, x, y, val);
	}
};

long long get_x(node_x *u, int lt, int rt, int lx, int rx, int ly, int ry) {
	if (!u) {
		return 0LL;
	}
	if (lt == lx && rt == rx) {
		return get_y(u->root_y, ly, ry);
	}
	int mt = (lt + rt) >> 1;
	if (rx <= mt) {
		return get_x(u->lch, lt, mt, lx, rx, ly, ry);
	}
	else if (lx >= mt + 1) {
		return get_x(u->rch, mt + 1, rt, lx, rx, ly, ry);
	}
	else {
		return __gcd(get_x(u->lch, lt, mt, lx, mt, ly, ry), get_x(u->rch, mt + 1, rt, mt + 1, rx, ly, ry));
	}
}

int n, m;
node_x *root_x = nullptr;

void init(int _n, int _m) {
	n = _n;
	m = _m;
}

void update(int x, int y, long long val) {
	x++;
	y++;
	update_x(root_x, 1, n, x, y, val);
}

long long calculate(int lx, int ly, int rx, int ry) {
	lx++;
	ly++;
	rx++;
	ry++;
	return get_x(root_x, 1, n, lx, rx, ly, ry);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 675 ms 9840 KB Output is correct
5 Correct 287 ms 11416 KB Output is correct
6 Correct 1022 ms 8708 KB Output is correct
7 Correct 1156 ms 8616 KB Output is correct
8 Correct 774 ms 7544 KB Output is correct
9 Correct 1122 ms 8784 KB Output is correct
10 Correct 1000 ms 8284 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1148 ms 13684 KB Output is correct
13 Correct 3059 ms 12300 KB Output is correct
14 Correct 497 ms 13108 KB Output is correct
15 Correct 3218 ms 13684 KB Output is correct
16 Correct 348 ms 12884 KB Output is correct
17 Correct 1620 ms 10460 KB Output is correct
18 Correct 2746 ms 14640 KB Output is correct
19 Correct 2353 ms 14480 KB Output is correct
20 Correct 2369 ms 13788 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 706 ms 9728 KB Output is correct
13 Correct 284 ms 11228 KB Output is correct
14 Correct 994 ms 8744 KB Output is correct
15 Correct 1117 ms 8448 KB Output is correct
16 Correct 771 ms 7384 KB Output is correct
17 Correct 1093 ms 8632 KB Output is correct
18 Correct 987 ms 8220 KB Output is correct
19 Correct 1134 ms 15668 KB Output is correct
20 Correct 2990 ms 12496 KB Output is correct
21 Correct 499 ms 13116 KB Output is correct
22 Correct 3149 ms 13380 KB Output is correct
23 Correct 352 ms 12960 KB Output is correct
24 Correct 1585 ms 10156 KB Output is correct
25 Correct 2755 ms 14448 KB Output is correct
26 Correct 2302 ms 14476 KB Output is correct
27 Correct 2325 ms 14044 KB Output is correct
28 Correct 776 ms 36272 KB Output is correct
29 Correct 1555 ms 38992 KB Output is correct
30 Correct 4101 ms 30420 KB Output is correct
31 Correct 3518 ms 29816 KB Output is correct
32 Correct 683 ms 29320 KB Output is correct
33 Correct 1042 ms 29312 KB Output is correct
34 Correct 373 ms 32716 KB Output is correct
35 Correct 1915 ms 23904 KB Output is correct
36 Correct 3174 ms 37032 KB Output is correct
37 Correct 2611 ms 37320 KB Output is correct
38 Correct 2657 ms 36420 KB Output is correct
39 Correct 2200 ms 30880 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 380 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 694 ms 9432 KB Output is correct
13 Correct 290 ms 11348 KB Output is correct
14 Correct 983 ms 8792 KB Output is correct
15 Correct 1119 ms 8492 KB Output is correct
16 Correct 766 ms 7672 KB Output is correct
17 Correct 1104 ms 9040 KB Output is correct
18 Correct 991 ms 8528 KB Output is correct
19 Correct 1138 ms 15524 KB Output is correct
20 Correct 3068 ms 12432 KB Output is correct
21 Correct 484 ms 13084 KB Output is correct
22 Correct 3118 ms 13132 KB Output is correct
23 Correct 347 ms 12820 KB Output is correct
24 Correct 1610 ms 10308 KB Output is correct
25 Correct 2751 ms 14896 KB Output is correct
26 Correct 2286 ms 14524 KB Output is correct
27 Correct 2317 ms 14376 KB Output is correct
28 Correct 753 ms 36352 KB Output is correct
29 Correct 1540 ms 39072 KB Output is correct
30 Correct 4070 ms 30124 KB Output is correct
31 Correct 3533 ms 30128 KB Output is correct
32 Correct 681 ms 29524 KB Output is correct
33 Correct 1000 ms 29408 KB Output is correct
34 Correct 366 ms 32776 KB Output is correct
35 Correct 1756 ms 23988 KB Output is correct
36 Correct 3134 ms 36748 KB Output is correct
37 Correct 2569 ms 37452 KB Output is correct
38 Correct 2653 ms 36532 KB Output is correct
39 Correct 1069 ms 65616 KB Output is correct
40 Correct 2629 ms 67804 KB Output is correct
41 Correct 6289 ms 57464 KB Output is correct
42 Correct 5750 ms 55604 KB Output is correct
43 Correct 635 ms 62292 KB Output is correct
44 Correct 1214 ms 52908 KB Output is correct
45 Correct 2203 ms 31068 KB Output is correct
46 Correct 3973 ms 66672 KB Output is correct
47 Correct 3960 ms 66392 KB Output is correct
48 Correct 3986 ms 66352 KB Output is correct
49 Correct 0 ms 348 KB Output is correct