oj.uz

Submission #364071

# Submission time Handle Problem Language Result Execution time Memory
364071 2021-02-08T08:03:55 Z Temmie Game (IOI13_game) C++17
63 / 100
 2834 ms 256004 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) : ret);
		if (row.second > mid) ret = (r ? gcd(ret, r->get(row)) : ret);
		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) : ret);
		if (col.second > mid) ret = (r ? gcd(ret, r->get(row, col)) : ret);
		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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1710 ms 79528 KB Output is correct
5 Correct 1484 ms 79012 KB Output is correct
6 Correct 1873 ms 77452 KB Output is correct
7 Correct 2293 ms 77256 KB Output is correct
8 Correct 1218 ms 48304 KB Output is correct
9 Correct 2097 ms 77672 KB Output is correct
10 Correct 2161 ms 77320 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1615 ms 29676 KB Output is correct
13 Correct 2184 ms 16868 KB Output is correct
14 Correct 604 ms 5996 KB Output is correct
15 Correct 2478 ms 23916 KB Output is correct
16 Correct 1069 ms 38312 KB Output is correct
17 Correct 2021 ms 28268 KB Output is correct
18 Correct 2834 ms 39656 KB Output is correct
19 Correct 2464 ms 39976 KB Output is correct
20 Correct 2382 ms 39264 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1835 ms 79376 KB Output is correct
13 Correct 1567 ms 79124 KB Output is correct
14 Correct 1919 ms 77712 KB Output is correct
15 Correct 2209 ms 77496 KB Output is correct
16 Correct 1176 ms 48108 KB Output is correct
17 Correct 2054 ms 77864 KB Output is correct
18 Correct 2075 ms 77172 KB Output is correct
19 Correct 1608 ms 29676 KB Output is correct
20 Correct 2154 ms 16816 KB Output is correct
21 Correct 570 ms 6096 KB Output is correct
22 Correct 2482 ms 24004 KB Output is correct
23 Correct 982 ms 38412 KB Output is correct
24 Correct 1604 ms 28176 KB Output is correct
25 Correct 2576 ms 39892 KB Output is correct
26 Correct 2411 ms 39864 KB Output is correct
27 Correct 2216 ms 39428 KB Output is correct
28 Runtime error 699 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1675 ms 79444 KB Output is correct
13 Correct 1447 ms 79156 KB Output is correct
14 Correct 1822 ms 77416 KB Output is correct
15 Correct 2203 ms 77608 KB Output is correct
16 Correct 1229 ms 48200 KB Output is correct
17 Correct 2094 ms 77676 KB Output is correct
18 Correct 2144 ms 77208 KB Output is correct
19 Correct 1616 ms 29676 KB Output is correct
20 Correct 2168 ms 17028 KB Output is correct
21 Correct 575 ms 6004 KB Output is correct
22 Correct 2466 ms 24228 KB Output is correct
23 Correct 991 ms 38380 KB Output is correct
24 Correct 1659 ms 28460 KB Output is correct
25 Correct 2589 ms 39996 KB Output is correct
26 Correct 2299 ms 39940 KB Output is correct
27 Correct 2221 ms 39492 KB Output is correct
28 Runtime error 683 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -