oj.uz

Submission #364067

# Submission time Handle Problem Language Result Execution time Memory
364067 2021-02-08T07:58:55 Z Temmie Game (IOI13_game) C++17
0 / 100
 2 ms 876 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 2 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 2 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 2 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 2 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -