Submission #729385

#	Time	Username	Problem	Language	Result	Execution time	Memory
729385		kevlu8	Game (IOI13_game)	C++17	100 / 100	3003 ms	82228 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n, m, q;

struct node1d {
	node1d(int v, int x, int y) : v(v), x(x), y(y), l(NULL), r(NULL) {}
	ll v;
	int x, y; // range
	node1d *l, *r;
};

struct node2d {
	node2d() : l(NULL), r(NULL), segtree(0, 1, m) {}
	node2d *l, *r;
	node1d segtree;
} *root;

void update1d(node1d *root, int i, ll v) {
	int s = root->x, e = root->y, mid = (s + e) >> 1;
	if (s == e) {
		root->v = v;
		return;
	}
	node1d **child = &(i <= mid ? root->l : root->r);
	if (*child == NULL) {
		*child = new node1d(v, i, i);
		(*child)->v = v;
	} else if ((*child)->x <= i && i <= (*child)->y) {
		update1d(*child, i, v);
	} else {
		do {
			if (i <= mid) e = mid;
			else s = mid + 1;
			mid = (s + e) >> 1;
		} while ((i <= mid) == ((*child)->y <= mid));
		node1d *node2 = new node1d(0, s, e);
		if ((*child)->y <= mid) node2->l = *child;
		else node2->r = *child;
		*child = node2;
		update1d(*child, i, v);
	}
	root->v = __gcd(root->l ? root->l->v : 0, root->r ? root->r->v : 0);
}

ll calculate1d(node1d *root, int l, int r) {
	if (root == NULL || root->x > r || root->y < l) return 0;
	if (l <= root->x && root->y <= r) {
		return root->v;
	}
	return __gcd(calculate1d(root->l, l, r), calculate1d(root->r, l, r));
}

void update2d(node2d *root, int l, int r, int x, int y, ll v) {
	if (l == r) {
		update1d(&root->segtree, y, v);
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		if (root->l == NULL) root->l = new node2d();
		update2d(root->l, l, mid, x, y, v);
	} else {
		if (root->r == NULL) root->r = new node2d();
		update2d(root->r, mid+1, r, x, y, v);
	}
	ll value = __gcd(root->l ? calculate1d(&root->l->segtree, y, y) : 0, root->r ? calculate1d(&root->r->segtree, y, y) : 0);
	update1d(&root->segtree, y, value);
}

ll calculate2d(node2d *root, int l, int r, int x, int y, int x2, int y2) {
	if (root == NULL || l > x2 || r < x) return 0; 
	if (x <= l && r <= x2) return calculate1d(&root->segtree, y, y2);
	int mid = (l + r) >> 1;
	return __gcd(calculate2d(root->l, l, mid, x, y, x2, y2), calculate2d(root->r, mid+1, r, x, y, x2, y2));
}

void init(int n, int m) {
	::n = n;
	::m = m;
	root = new node2d();
}

void update(int x, int y, ll v) {
	++x, ++y;
	update2d(root, 1, n, x, y, v);
}

ll calculate(int x, int y, int x2, int y2) {
	++x, ++y, ++x2, ++y2;
	return calculate2d(root, 1, n, x, y, x2, y2);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20