oj.uz

Submission #330043

# Submission time Handle Problem Language Result Execution time Memory
330043 2020-11-23T14:06:16 Z rk42745417 Game (IOI13_game) C++17
63 / 100
 1958 ms 256004 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

struct tree_node {
	int l = -1, r = -1;
	ll v;
	tree_node(ll _v) { v = _v; }
};
vector<tree_node> nodes;
int segtree_t;

struct segtree {
	int n, root = -1;
	void init(int c) { n = c; }
	void edt(int p, ll v) {
		root = edt(0, n, root, p, v);
	}
	int edt(int l, int r, int id, int p, ll v) {
		if(r <= p || p < l)
			return id;
		if(id == -1) {
			nodes.push_back(tree_node(0));
			id = segtree_t++;
		}
		if(l == r - 1) {
			nodes[id].v = v;
			return id;
		}
		int m = l + r >> 1;
		nodes[id].l = edt(l, m, nodes[id].l, p, v);
		nodes[id].r = edt(m, r, nodes[id].r, p, v);
		nodes[id].v = 0;
		if(~nodes[id].l)
			nodes[id].v = nodes[nodes[id].l].v;
		if(~nodes[id].r)
			nodes[id].v = __gcd(nodes[id].v, nodes[nodes[id].r].v);
		return id;
	}
	ll que(int l, int r) {
		return que(0, n, root, l, r);
	}
	ll que(int l, int r, int id, int ql, int qr) {
		if(qr <= l || r <= ql || id == -1)
			return 0;
		if(ql <= l && r <= qr)
			return nodes[id].v;
		int m = l + r >> 1;
		return __gcd(que(l, m, nodes[id].l, ql, qr), que(m, r, nodes[id].r, ql, qr));
	}
};
struct two_d_segtree {
	int nr, nc, t = 0, root = -1;
	struct node {
		int l = -1, r = -1;
		segtree v;
		node(int c) { v.init(c); }
	};
	vector<node> arr;
	void init(int x, int y) { nr = x, nc = y; }
	void edt(int x, int y, ll v) {
		root = edt(0, nr, x, y, root, v);
	}
	int edt(int l, int r, int x, int y, int id, ll v) {
		if(l > x || r <= x)
			return id;
		if(id == -1) {
			arr.push_back(node(nc));
			id = t++;
		}
		if(l == r - 1) {
			arr[id].v.edt(y, v);
			return id;
		}
		int m = l + r >> 1;
		arr[id].l = edt(l, m, x, y, arr[id].l, v);
		arr[id].r = edt(m, r, x, y, arr[id].r, v);
		arr[id].v.edt(y, __gcd(~arr[id].l ? arr[arr[id].l].v.que(y, y + 1) : 0, ~arr[id].r ? arr[arr[id].r].v.que(y, y + 1) : 0));
		return id;
	}
	ll que(int x1, int y1, int x2, int y2) {
		return que(0, nr, root, x1, x2, y1, y2);
	}
	ll que(int l, int r, int id, int x1, int x2, int y1, int y2) {
		if(r <= x1 || x2 <= l || id == -1)
			return 0;
		if(x1 <= l && r <= x2)
			return arr[id].v.que(y1, y2);
		int m = l + r >> 1;
		return __gcd(que(l, m, arr[id].l, x1, x2, y1, y2), que(m, r, arr[id].r, x1, x2, y1, y2));
	}
} tree;

#include "game.h"

void init(int r, int c) {
	tree.init(r, c);
}
void update(int p, int q, long long k) {
	tree.edt(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
	if(p > u)
		swap(p, u);
	if(q > v)
		swap(q, v);
	return tree.que(p, q, u + 1, v + 1);
}

/*
signed main() { EmiliaMyWife
	int r, c, n;
	cin >> r >> c >> n;
	init(r, c);
	while(n--) {
		int t;
		cin >> t;
		if(t == 1) {
			int x, y;
			ll k;
			cin >> x >> y >> k;
			//tree.edt(x, y, k);
			update(x, y, k);
		}
		else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			cout << calculate(a, b, c, d) << '\n';
			//if(a > c)
				//swap(a, c);
			//if(b > d)
				//swap(b, d);
			//cout << tree.que(a, b, c + 1, d + 1) << '\n';
			//cout << "0\n";
		}
	}
}
*/

Compilation message

game.cpp: In member function 'int segtree::edt(int, int, int, int, ll)':
game.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'll segtree::que(int, int, int, int, int)':
game.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'int two_d_segtree::edt(int, int, int, int, int, ll)':
game.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'll two_d_segtree::que(int, int, int, int, int, int, int)':
game.cpp:110:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 575 ms 12712 KB Output is correct
5 Correct 426 ms 13012 KB Output is correct
6 Correct 518 ms 9940 KB Output is correct
7 Correct 558 ms 8660 KB Output is correct
8 Correct 415 ms 5980 KB Output is correct
9 Correct 544 ms 9044 KB Output is correct
10 Correct 512 ms 8660 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 872 ms 11476 KB Output is correct
13 Correct 1369 ms 4572 KB Output is correct
14 Correct 328 ms 1004 KB Output is correct
15 Correct 1637 ms 5064 KB Output is correct
16 Correct 237 ms 16840 KB Output is correct
17 Correct 822 ms 9880 KB Output is correct
18 Correct 1449 ms 17364 KB Output is correct
19 Correct 1179 ms 18068 KB Output is correct
20 Correct 1126 ms 17436 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 572 ms 12840 KB Output is correct
13 Correct 405 ms 13012 KB Output is correct
14 Correct 485 ms 9812 KB Output is correct
15 Correct 538 ms 8660 KB Output is correct
16 Correct 428 ms 5980 KB Output is correct
17 Correct 532 ms 9076 KB Output is correct
18 Correct 492 ms 8660 KB Output is correct
19 Correct 875 ms 11348 KB Output is correct
20 Correct 1384 ms 4572 KB Output is correct
21 Correct 495 ms 1004 KB Output is correct
22 Correct 1653 ms 4976 KB Output is correct
23 Correct 254 ms 16840 KB Output is correct
24 Correct 855 ms 9868 KB Output is correct
25 Correct 1453 ms 17504 KB Output is correct
26 Correct 1148 ms 18164 KB Output is correct
27 Correct 1079 ms 17476 KB Output is correct
28 Correct 933 ms 135628 KB Output is correct
29 Runtime error 1958 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 557 ms 12648 KB Output is correct
13 Correct 404 ms 13012 KB Output is correct
14 Correct 485 ms 9948 KB Output is correct
15 Correct 524 ms 8664 KB Output is correct
16 Correct 365 ms 6108 KB Output is correct
17 Correct 526 ms 9172 KB Output is correct
18 Correct 498 ms 8968 KB Output is correct
19 Correct 860 ms 11348 KB Output is correct
20 Correct 1375 ms 4572 KB Output is correct
21 Correct 317 ms 1132 KB Output is correct
22 Correct 1640 ms 5048 KB Output is correct
23 Correct 242 ms 16840 KB Output is correct
24 Correct 798 ms 9940 KB Output is correct
25 Correct 1389 ms 17536 KB Output is correct
26 Correct 1160 ms 17992 KB Output is correct
27 Correct 1084 ms 17620 KB Output is correct
28 Correct 943 ms 135516 KB Output is correct
29 Runtime error 1929 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -