Submission #382898

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
382898	2021-03-28T11:28:05 Z	rk42745417	Game (IOI13_game)	C++17	100 / 100	7663 ms	182716 KB

game

/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     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;
/*--------------------------------------------------------------------------------------*/

#include "game.h"
const int N = 1e6 + 25;

mt19937 rnd(time(0));
struct segtree {
	struct Treap {
		struct node {
			int l, r, key, pri;
			ll v, gd;
			node(): l(0), r(0), key(0), pri(0), v(0), gd(0) { }
			node(int p): l(0), r(0), key(p), pri(rnd()), v(0), gd(0) { }
		} arr[N * 5];
		int t = 1;
		inline int new_node(int x) {
			arr[t] = node(x);
			assert(t <= N * 5);
			return t++;
		}
		inline ll gd(int p) { return p ? arr[p].gd : 0; }
		inline void pull(int p) { arr[p].gd = __gcd(__gcd(gd(arr[p].l), arr[p].v), gd(arr[p].r)); }
		int merge(int a, int b) {
			if(!a || !b)
				return a ? a : b;
			//assert(arr[a].key < arr[b].key);
			if(arr[a].pri > arr[b].pri) {
				arr[a].r = merge(arr[a].r, b);
				pull(a);
				return a;
			}
			else {
				arr[b].l = merge(a, arr[b].l);
				pull(b);
				return b;
			}
		}
		void split(int rt, int &a, int &b, int k) {
			if(!rt)
				return a = b = 0, void();
			if(arr[rt].key < k) {
				 a = rt;
				 split(arr[rt].r, arr[a].r, b, k);
				 pull(a);
			}
			else {
				b = rt;
				split(arr[rt].l, a, arr[b].l, k);
				pull(b);
			}
		}
		void travesal(int p) {
			if(!p)
				return;
			travesal(arr[p].l);
			cout << arr[p].v << ' ';
			travesal(arr[p].r);
		}
		int edt(int rt, int p, ll v) {
			int a, b, c;
			split(rt, b, c, p + 1);
			split(b, a, b, p);
			if(!b)
				b = new_node(p);
			arr[b].v = arr[b].gd = v;
			rt = merge(a, b);
			rt = merge(rt, c);
			return rt;
		}
		ll que(int rt, int l, int r) { // [l, r)
			int a, b, c;
			split(rt, b, c, r);
			split(b, a, b, l);
			ll x = arr[b].gd;
			rt = merge(a, b);
			rt = merge(rt, c);
			return x;
		}
	} treap;

	struct node {
		int l, r, v;
		node(): l(0), r(0), v(0) { }
	} arr[N];
	int r, c, t = 1, rt;
	void init(int _r, int _c) {
		r = _r;
		c = _c;
	}
	int edt(int id, int l, int r, int p, int q, ll v) {
		if(p < l || r <= p)
			return id;
		if(!id)
			id = t++, assert(t < N);
		if(l == r - 1) {
			arr[id].v = treap.edt(arr[id].v, q, v);
			return id;
		}
		int m = l + r >> 1;
		arr[id].l = edt(arr[id].l, l, m, p, q, v);
		arr[id].r = edt(arr[id].r, m, r, p, q, v);
		
		ll x = 0;
		if(arr[id].l)
			x = treap.que(arr[arr[id].l].v, q, q + 1);
		if(arr[id].r)
			x = __gcd(x, treap.que(arr[arr[id].r].v, q, q + 1));
		arr[id].v = treap.edt(arr[id].v, q, x);
		return id;
	}
	ll que(int id, int l, int r, int ql, int qr, int up, int dw) {
		if(r <= ql || qr <= l || !id)
			return 0;
		if(ql <= l && r <= qr) {
			//cout << l << ' ' << r << ' ' << up << ' ' << dw << '\n';
			return treap.que(arr[id].v, up, dw);
		}
		int m = l + r >> 1;
		return __gcd(que(arr[id].l, l, m, ql, qr, up, dw), que(arr[id].r, m, r, ql, qr, up, dw));
	}
	inline void edt(int p, int q, ll v) { rt = edt(rt, 0, r, p, q, v); }
	inline ll que(int p, int q, int u, int v) { return que(rt, 0, r, p, u, q, v); }
} tree;

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) {
	return tree.que(p, q, u + 1, v + 1);
}

/*
signed main() { EmiliaMyWife
	int r, c, q;
	cin >> r >> c >> q;
	init(r, c);
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int p, q; ll k;
			cin >> p >> q >> k;
			update(p, q, k);
		}
		else {
			int p, q, u, v;
			cin >> p >> q >> u >> v;
			cout << calculate(p, q, u, v) << '\n';
		}
	}
}
*/

Compilation message

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

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	168684 KB	Output is correct
2	Correct	97 ms	168684 KB	Output is correct
3	Correct	96 ms	168684 KB	Output is correct
4	Correct	100 ms	168684 KB	Output is correct
5	Correct	96 ms	168684 KB	Output is correct
6	Correct	99 ms	168684 KB	Output is correct
7	Correct	96 ms	168684 KB	Output is correct
8	Correct	97 ms	168684 KB	Output is correct
9	Correct	99 ms	168684 KB	Output is correct
10	Correct	96 ms	168684 KB	Output is correct
11	Correct	97 ms	168684 KB	Output is correct
12	Correct	96 ms	168684 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	168684 KB	Output is correct
2	Correct	96 ms	168684 KB	Output is correct
3	Correct	96 ms	168684 KB	Output is correct
4	Correct	1222 ms	177132 KB	Output is correct
5	Correct	636 ms	177004 KB	Output is correct
6	Correct	1677 ms	174572 KB	Output is correct
7	Correct	1904 ms	174060 KB	Output is correct
8	Correct	1285 ms	174700 KB	Output is correct
9	Correct	1847 ms	174344 KB	Output is correct
10	Correct	1716 ms	174056 KB	Output is correct
11	Correct	97 ms	168684 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	168716 KB	Output is correct
2	Correct	102 ms	168684 KB	Output is correct
3	Correct	99 ms	168684 KB	Output is correct
4	Correct	98 ms	168684 KB	Output is correct
5	Correct	97 ms	168684 KB	Output is correct
6	Correct	99 ms	168684 KB	Output is correct
7	Correct	98 ms	168684 KB	Output is correct
8	Correct	99 ms	168684 KB	Output is correct
9	Correct	98 ms	168684 KB	Output is correct
10	Correct	98 ms	168684 KB	Output is correct
11	Correct	99 ms	168812 KB	Output is correct
12	Correct	1917 ms	176960 KB	Output is correct
13	Correct	3819 ms	173392 KB	Output is correct
14	Correct	647 ms	173932 KB	Output is correct
15	Correct	4198 ms	173968 KB	Output is correct
16	Correct	662 ms	173840 KB	Output is correct
17	Correct	2636 ms	174776 KB	Output is correct
18	Correct	4445 ms	175084 KB	Output is correct
19	Correct	3825 ms	175376 KB	Output is correct
20	Correct	3755 ms	174644 KB	Output is correct
21	Correct	104 ms	168684 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	168684 KB	Output is correct
2	Correct	103 ms	168684 KB	Output is correct
3	Correct	101 ms	168684 KB	Output is correct
4	Correct	103 ms	168684 KB	Output is correct
5	Correct	98 ms	168684 KB	Output is correct
6	Correct	101 ms	168684 KB	Output is correct
7	Correct	99 ms	168684 KB	Output is correct
8	Correct	98 ms	168684 KB	Output is correct
9	Correct	100 ms	168684 KB	Output is correct
10	Correct	99 ms	168684 KB	Output is correct
11	Correct	104 ms	168636 KB	Output is correct
12	Correct	1244 ms	177260 KB	Output is correct
13	Correct	633 ms	177004 KB	Output is correct
14	Correct	1678 ms	174572 KB	Output is correct
15	Correct	1900 ms	174408 KB	Output is correct
16	Correct	1271 ms	174444 KB	Output is correct
17	Correct	1846 ms	174316 KB	Output is correct
18	Correct	1715 ms	173820 KB	Output is correct
19	Correct	1904 ms	176776 KB	Output is correct
20	Correct	3752 ms	173304 KB	Output is correct
21	Correct	635 ms	173932 KB	Output is correct
22	Correct	4126 ms	173864 KB	Output is correct
23	Correct	683 ms	173548 KB	Output is correct
24	Correct	2639 ms	175008 KB	Output is correct
25	Correct	4375 ms	175264 KB	Output is correct
26	Correct	3833 ms	175272 KB	Output is correct
27	Correct	3709 ms	174604 KB	Output is correct
28	Correct	1529 ms	180188 KB	Output is correct
29	Correct	2551 ms	182508 KB	Output is correct
30	Correct	4826 ms	176308 KB	Output is correct
31	Correct	4475 ms	176464 KB	Output is correct
32	Correct	923 ms	178460 KB	Output is correct
33	Correct	1272 ms	178352 KB	Output is correct
34	Correct	972 ms	176236 KB	Output is correct
35	Correct	2963 ms	179872 KB	Output is correct
36	Correct	5536 ms	180372 KB	Output is correct
37	Correct	4450 ms	180844 KB	Output is correct
38	Correct	4632 ms	179992 KB	Output is correct
39	Correct	3742 ms	180432 KB	Output is correct
40	Correct	97 ms	168684 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	168684 KB	Output is correct
2	Correct	99 ms	168684 KB	Output is correct
3	Correct	99 ms	168684 KB	Output is correct
4	Correct	98 ms	168684 KB	Output is correct
5	Correct	97 ms	168684 KB	Output is correct
6	Correct	99 ms	168684 KB	Output is correct
7	Correct	100 ms	168684 KB	Output is correct
8	Correct	98 ms	168684 KB	Output is correct
9	Correct	99 ms	168684 KB	Output is correct
10	Correct	98 ms	168684 KB	Output is correct
11	Correct	99 ms	168684 KB	Output is correct
12	Correct	1277 ms	177352 KB	Output is correct
13	Correct	631 ms	177004 KB	Output is correct
14	Correct	1683 ms	174532 KB	Output is correct
15	Correct	1925 ms	174316 KB	Output is correct
16	Correct	1303 ms	174788 KB	Output is correct
17	Correct	1872 ms	174808 KB	Output is correct
18	Correct	1702 ms	173804 KB	Output is correct
19	Correct	1818 ms	177080 KB	Output is correct
20	Correct	3861 ms	173316 KB	Output is correct
21	Correct	649 ms	173932 KB	Output is correct
22	Correct	4034 ms	173868 KB	Output is correct
23	Correct	694 ms	173544 KB	Output is correct
24	Correct	2676 ms	174900 KB	Output is correct
25	Correct	4428 ms	175084 KB	Output is correct
26	Correct	3955 ms	175608 KB	Output is correct
27	Correct	3838 ms	174660 KB	Output is correct
28	Correct	1491 ms	179948 KB	Output is correct
29	Correct	2590 ms	182716 KB	Output is correct
30	Correct	4976 ms	176432 KB	Output is correct
31	Correct	4494 ms	176456 KB	Output is correct
32	Correct	910 ms	178460 KB	Output is correct
33	Correct	1257 ms	178540 KB	Output is correct
34	Correct	827 ms	176108 KB	Output is correct
35	Correct	2873 ms	179820 KB	Output is correct
36	Correct	5347 ms	180332 KB	Output is correct
37	Correct	4335 ms	180552 KB	Output is correct
38	Correct	4462 ms	179828 KB	Output is correct
39	Correct	2183 ms	180100 KB	Output is correct
40	Correct	4282 ms	182288 KB	Output is correct
41	Correct	7571 ms	176724 KB	Output is correct
42	Correct	6990 ms	176708 KB	Output is correct
43	Correct	1868 ms	176620 KB	Output is correct
44	Correct	1430 ms	178924 KB	Output is correct
45	Correct	3727 ms	180204 KB	Output is correct
46	Correct	7444 ms	180852 KB	Output is correct
47	Correct	7663 ms	180700 KB	Output is correct
48	Correct	7442 ms	180464 KB	Output is correct
49	Correct	101 ms	168684 KB	Output is correct