Submission #364067

#	Time	Username	Problem	Language	Result	Execution time	Memory
364067		Temmie	Game (IOI13_game)	C++17	0 / 100	2 ms	876 KiB

game

#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

ll gcd(ll x, ll y) {
	ll z;
	while (x != y && y != 0) z = x, x = y, y = z % y;
	return x;
}

const int size = 1 << 30;

struct Row {
	
	Row* l = nullptr, * r = nullptr;
	ll d;
	
	std::pair <int, int> span;
	
	int mid;
	
	Row (const std::pair <int, int>& SPAN) :
	d(0),
	span(SPAN),
	mid((SPAN.first + SPAN.second) >> 1)
	{ }
	
	~Row() {
		if (l) delete(l);
		if (r) delete(r);
	}
	
	ll get(const std::pair <int, int>& row) {
		if (span.first >= row.first && span.second <= row.second) return d;
		ll ret = 0;
		if (row.first <= mid) ret = (l ? l->get(row) : 0);
		if (row.second > mid) ret = (r ? gcd(ret, r->get(row)) : 0);
		return ret;
	}
	
	void set(int row, ll val) {
		if (span.first == span.second) {
			d = val;
			return;
		}
		if (row <= mid) {
			if (!l) l = new Row({ span.first, mid });
			l->set(row, val);
			d = gcd(r ? r->d : 0, l->d);
		} else {
			if (!r) r = new Row({ mid + 1, span.second });
			r->set(row, val);
			d = gcd(l ? l->d : 0, r->d);
		}
	}
	
	void merge(int row, Row* r1, Row* r2) {
		if (span.first == span.second) {
			d = gcd(r1 ? r1->d : 0, r2 ? r2->d : 0);
			return;
		}
		if (row <= mid) {
			if (!l) l = new Row({ span.first, mid });
			d = gcd(r1 ? r1->d : 0, r2 ? r2->d : 0);
			l->merge(row, r1 ? r1->l : nullptr, r2 ? r2->l : nullptr);
		} else {
			if (!r) r = new Row({ mid + 1, span.second });
			d = gcd(r1 ? r1->d : 0, r2 ? r2->d : 0);
			r->merge(row, r1 ? r1->r : nullptr, r2 ? r2->r : nullptr);
		}
	}
	
};

struct Col {
	
	Col* l = nullptr, * r = nullptr;
	Row* d = nullptr;
	
	std::pair <int, int> span;
	
	int mid;
	
	Col (const std::pair <int, int>& SPAN) :
	span(SPAN),
	mid((SPAN.first + SPAN.second) >> 1)
	{
		d = new Row({ 0, size });
	}
	
	~Col() {
		if (l) delete(l);
		if (r) delete(r);
		if (d) delete(d);
	}
	
	ll get(const std::pair <int, int>& row, const std::pair <int, int>& col) {
		if (span.first >= col.first && span.second <= col.second) return d->get(row);
		ll ret = 0;
		if (col.first <= mid) ret = (l ? l->get(row, col) : 0);
		if (col.second > mid) ret = (r ? gcd(ret, r->get(row, col)) : 0);
		return ret;
	}
	
	void set(int row, int col, ll val) {
		if (span.first == span.second) {
			d->set(row, val);
			return;
		}
		if (col <= mid) {
			if (!l) l = new Col({ span.first, mid });
			l->set(row, col, val);
		} else {
			if (!r) r = new Col({ mid + 1, span.second });
			r->set(row, col, val);
		}
		d->merge(row, l ? l->d : nullptr, r ? r->d : nullptr);
	}
	
};

Col* tree = nullptr;

void init(int r, int c) {
	tree = new Col({ 0, size });
}

void update(int r, int c, ll val) {
	tree->set(r, c, val);
}

ll calculate(int r1, int c1, int r2, int c2) {
	return tree->get({ r1, r2 }, { c1, c2 });
}

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