oj.uz

Submission #590256

# Submission time Handle Problem Language Result Execution time Memory
590256 2022-07-05T17:07:00 Z Temmie Game (IOI13_game) C++17
100 / 100
 3199 ms 161800 KB 
#include "game.h"
#include <bits/stdc++.h>

constexpr const int MX_RC = 1 << 30;

struct Inner {
	
	long long val;
	int lv, rv;
	Inner* lc,* rc;
	
	Inner(long long _val, int _l, int _r) :
	val(_val), lv(_l), rv(_r), lc(nullptr), rc(nullptr)
	{ }
	
	~Inner() {
		delete(lc);
		delete(rc);
	}
	
	void update(int ind, long long nev, int l = 0, int r = MX_RC) {
		if (!(r - l - 1)) {
			assert(lv == l && rv == r);
			assert(ind == l);
			val = nev;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) {
			if (lc) {
				if (lc->lv != l || lc->rv != mid) {
					Inner* tmp = lc;
					lc = new Inner(0, l, mid);
					(tmp->lv < ((l + mid) >> 1) ? lc->lc : lc->rc) = tmp;
				}
				lc->update(ind, nev, l, mid);
			} else {
				lc = new Inner(nev, ind, ind + 1);
			}
		} else {
			if (rc) {
				if (rc->lv != mid || rc->rv != r) {
					Inner* tmp = rc;
					rc = new Inner(0, mid, r);
					(tmp->lv < ((mid + r) >> 1) ? rc->lc : rc->rc) = tmp;
				}
				rc->update(ind, nev, mid, r);
			} else {
				rc = new Inner(nev, ind, ind + 1);
			}
		}
		val = std::gcd(lc ? lc->val : 0, rc ? rc->val : 0);
	}
	
	long long query(int tl, int tr, int l = 0, int r = MX_RC) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		if (!(rv - lv - 1)) {
			if (lv >= tr || rv <= tl) {
				return 0;
			}
			return val;
		}
		assert(l == lv && r == rv);
		if (l >= tl && r <= tr) {
			return val;
		}
		int mid = (l + r) >> 1;
		return std::gcd(lc ? lc->query(tl, tr, l, mid) : 0, rc ? rc->query(tl, tr, mid, r) : 0);
	}
	
	void fill(Inner* source) {
		val = source->val;
		if (!(lv - rv - 1)) {
			return;
		}
		if (source->lc) {
			lc = new Inner(source->lc->val, source->lc->lv, source->lc->rv);
			lc->fill(source->lc);
		}
		if (source->rc) {
			rc = new Inner(source->rc->val, source->rc->lv, source->rc->rv);
			rc->fill(source->rc);
		}
	}
	
};

struct Outer {
	
	Inner* inner;
	int lv, rv;
	Outer* lc,* rc;
	
	Outer(Inner* _inner, int _l, int _r) :
	inner(_inner), lv(_l), rv(_r), lc(nullptr), rc(nullptr)
	{ }
	
	void update(int ind_outer, int ind_inner, long long nev, int l = 0, int r = MX_RC) {
		if (!(r - l - 1)) {
			assert(lv == l && rv == r);
			assert(ind_outer == l);
			assert(inner);
			inner->update(ind_inner, nev);
			return;
		}
		int mid = (l + r) >> 1;
		if (ind_outer < mid) {
			if (lc) {
				if (lc->lv != l || lc->rv != mid) {
					Outer* tmp = lc;
					lc = new Outer(new Inner(0, 0, MX_RC), l, mid);
					lc->inner->fill(tmp->inner);
					(tmp->lv < ((l + mid) >> 1) ? lc->lc : lc->rc) = tmp;
				}
				lc->update(ind_outer, ind_inner, nev, l, mid);
			} else {
				lc = new Outer(new Inner(0, 0, MX_RC), ind_outer, ind_outer + 1);
				lc->inner->update(ind_inner, nev);
			}
		} else {
			if (rc) {
				if (rc->lv != mid || rc->rv != r) {
					Outer* tmp = rc;
					rc = new Outer(new Inner(0, 0, MX_RC), mid, r);
					rc->inner->fill(tmp->inner);
					(tmp->lv < ((mid + r) >> 1) ? rc->lc : rc->rc) = tmp;
				}
				rc->update(ind_outer, ind_inner, nev, mid, r);
			} else {
				rc = new Outer(new Inner(nev, 0, MX_RC), ind_outer, ind_outer + 1);
				rc->inner->update(ind_inner, nev);
			}
		}
		inner->update(ind_inner, std::gcd(
		lc ? lc->inner->query(ind_inner, ind_inner + 1) : 0,
		rc ? rc->inner->query(ind_inner, ind_inner + 1) : 0));
	}
	
	long long query(int tl_outer, int tr_outer, int tl_inner, int tr_inner, int l = 0, int r = MX_RC) {
		if (l >= tr_outer || r <= tl_outer) {
			return 0;
		}
		if (!(rv - lv - 1)) {
			if (lv >= tr_outer || rv <= tl_outer) {
				return 0;
			}
			return inner->query(tl_inner, tr_inner);
		}
		assert(l == lv && r == rv);
		if (l >= tl_outer && r <= tr_outer) {
			return inner->query(tl_inner, tr_inner);
		}
		int mid = (l + r) >> 1;
		return std::gcd(
		lc ? lc->query(tl_outer, tr_outer, tl_inner, tr_inner, l, mid) : 0,
		rc ? rc->query(tl_outer, tr_outer, tl_inner, tr_inner, mid, r) : 0);
	}
	
};

Outer root(new Inner(0, 0, MX_RC), 0, MX_RC);

void init(int r, int c) { }

void update(int r, int c, long long k) {
	root.update(r, c, k);
}

long long calculate(int r_l, int c_l, int r_r, int c_r) {
	return root.query(r_l, r_r + 1, c_l, c_r + 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 2 ms 684 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 678 ms 42536 KB Output is correct
5 Correct 568 ms 42348 KB Output is correct
6 Correct 698 ms 39868 KB Output is correct
7 Correct 769 ms 39512 KB Output is correct
8 Correct 522 ms 22676 KB Output is correct
9 Correct 794 ms 39512 KB Output is correct
10 Correct 781 ms 39180 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1344 ms 20780 KB Output is correct
13 Correct 1868 ms 14408 KB Output is correct
14 Correct 534 ms 5884 KB Output is correct
15 Correct 2203 ms 19772 KB Output is correct
16 Correct 737 ms 23000 KB Output is correct
17 Correct 1309 ms 18344 KB Output is correct
18 Correct 2411 ms 24416 KB Output is correct
19 Correct 1807 ms 24420 KB Output is correct
20 Correct 1567 ms 23976 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 706 ms 42376 KB Output is correct
13 Correct 578 ms 42268 KB Output is correct
14 Correct 723 ms 39780 KB Output is correct
15 Correct 723 ms 39480 KB Output is correct
16 Correct 469 ms 22760 KB Output is correct
17 Correct 747 ms 39420 KB Output is correct
18 Correct 711 ms 39132 KB Output is correct
19 Correct 1330 ms 20760 KB Output is correct
20 Correct 1721 ms 14432 KB Output is correct
21 Correct 496 ms 6008 KB Output is correct
22 Correct 1943 ms 19660 KB Output is correct
23 Correct 603 ms 22952 KB Output is correct
24 Correct 1051 ms 18460 KB Output is correct
25 Correct 1868 ms 24600 KB Output is correct
26 Correct 1603 ms 24588 KB Output is correct
27 Correct 1589 ms 23964 KB Output is correct
28 Correct 404 ms 37352 KB Output is correct
29 Correct 975 ms 32428 KB Output is correct
30 Correct 2470 ms 37932 KB Output is correct
31 Correct 2398 ms 81976 KB Output is correct
32 Correct 433 ms 10736 KB Output is correct
33 Correct 649 ms 14444 KB Output is correct
34 Correct 418 ms 26164 KB Output is correct
35 Correct 784 ms 19864 KB Output is correct
36 Correct 1499 ms 30408 KB Output is correct
37 Correct 1182 ms 30556 KB Output is correct
38 Correct 1105 ms 29800 KB Output is correct
39 Correct 943 ms 25388 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 556 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 676 ms 42488 KB Output is correct
13 Correct 544 ms 42244 KB Output is correct
14 Correct 742 ms 39856 KB Output is correct
15 Correct 764 ms 39492 KB Output is correct
16 Correct 496 ms 22776 KB Output is correct
17 Correct 721 ms 39464 KB Output is correct
18 Correct 757 ms 39212 KB Output is correct
19 Correct 1293 ms 20668 KB Output is correct
20 Correct 1751 ms 14612 KB Output is correct
21 Correct 472 ms 5876 KB Output is correct
22 Correct 1908 ms 19720 KB Output is correct
23 Correct 572 ms 22996 KB Output is correct
24 Correct 1004 ms 18456 KB Output is correct
25 Correct 1841 ms 24640 KB Output is correct
26 Correct 1534 ms 24492 KB Output is correct
27 Correct 1493 ms 23952 KB Output is correct
28 Correct 397 ms 37444 KB Output is correct
29 Correct 1016 ms 32460 KB Output is correct
30 Correct 2364 ms 37896 KB Output is correct
31 Correct 2258 ms 81904 KB Output is correct
32 Correct 417 ms 10612 KB Output is correct
33 Correct 597 ms 14372 KB Output is correct
34 Correct 419 ms 26240 KB Output is correct
35 Correct 745 ms 19796 KB Output is correct
36 Correct 1558 ms 30136 KB Output is correct
37 Correct 1214 ms 30564 KB Output is correct
38 Correct 1244 ms 29884 KB Output is correct
39 Correct 598 ms 73136 KB Output is correct
40 Correct 1606 ms 57080 KB Output is correct
41 Correct 3199 ms 74484 KB Output is correct
42 Correct 3121 ms 161800 KB Output is correct
43 Correct 664 ms 51600 KB Output is correct
44 Correct 561 ms 11052 KB Output is correct
45 Correct 899 ms 25468 KB Output is correct
46 Correct 1934 ms 55708 KB Output is correct
47 Correct 1936 ms 55728 KB Output is correct
48 Correct 1905 ms 55480 KB Output is correct
49 Correct 1 ms 340 KB Output is correct