Submission #382898

#	Time	Username	Problem	Language	Result	Execution time	Memory
382898		rk42745417	Game (IOI13_game)	C++17	100 / 100	7663 ms	182716 KiB

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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20