답안 #364071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364071	2021-02-08T08:03:55 Z	Temmie	게임 (IOI13_game)	C++17	63 / 100	2834 ms	256004 KB

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) : 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #364071

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0