Submission #1014966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014966	2024-07-05T19:52:06 Z	AmirAli_H1	Game (IOI13_game)	C++17	80 / 100	2663 ms	256000 KB

game

// In the name of Allah

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
const int maxs = 1e7 + 4;
ll t[maxs]; int tx[maxs];
int lc[maxs], rc[maxs], sz;

void set_val(int v, int u1, int u2, int tl, int tr, int i, int j, ll x) {
	if (tr - tl == 1) {
		if (tx[v] == -1) {
			t[v] = 0;
			if (u1 == -1 && u2 == -1) t[v] = x;
			else {
				if (u1 != -1) t[v] = __gcd(t[v], t[u1]);
				if (u2 != -1) t[v] = __gcd(t[v], t[u2]);
			}	
		}
		else {
			set_val(tx[v], -1, -1, 0, m, j, -1, x);
		}
		return ;
	}
	
	int mid = (tl + tr) / 2;
	if (i < mid) {
		if (lc[v] == -1) {
			int u = sz++; lc[v] = u;
			if (tx[v] != -1) tx[u] = sz++;
		}
		int x1 = u1, x2 = u2;
		if (x1 != -1) x1 = lc[x1];
		if (x2 != -1) x2 = lc[x2];
		set_val(lc[v], x1, x2, tl, mid, i, j, x);
	}
	else {
		if (rc[v] == -1) {
			int u = sz++; rc[v] = u;
			if (tx[v] != -1) tx[u] = sz++;
		}
		int x1 = u1, x2 = u2;
		if (x1 != -1) x1 = rc[x1];
		if (x2 != -1) x2 = rc[x2];
		set_val(rc[v], x1, x2, mid, tr, i, j, x);
	}
	
	t[v] = 0;
	if (tx[v] == -1) {
		if (lc[v] != -1) t[v] = __gcd(t[v], t[lc[v]]);
		if (rc[v] != -1) t[v] = __gcd(t[v], t[rc[v]]);
	}
	else {
		int x1 = -1, x2 = -1;
		if (lc[v] != -1) x1 = tx[lc[v]];
		if (rc[v] != -1) x2 = tx[rc[v]];
		set_val(tx[v], x1, x2, 0, m, j, -1, x);
	}
}

ll get_val(int v, int tl, int tr, int l, int r, int lx, int rx) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return 0;
	if (l == tl && r == tr) {
		if (tx[v] != -1) {
			return get_val(tx[v], 0, m, lx, rx, -1, -1);
		}
		else return t[v];
	}
	
	ll res = 0; int mid = (tl + tr) / 2;
	if (lc[v] != -1) res = __gcd(res, get_val(lc[v], tl, mid, l, r, lx, rx));
	if (rc[v] != -1) res = __gcd(res, get_val(rc[v], mid, tr, l, r, lx, rx));
	return res;
}

void init(int R, int C) {
	n = R; m = C;
	fill(tx, tx + maxs, -1);
	fill(lc, lc + maxs, -1); fill(rc, rc + maxs, -1);
	sz = 1; tx[0] = sz++;
	return ;
}

void update(int i, int j, ll x) {
	set_val(0, -1, -1, 0, n, i, j, x);
}

ll calculate(int l1, int l2, int r1, int r2) {
	r1++; r2++;
	return get_val(0, 0, n, l1, r1, l2, r2);
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	117852 KB	Output is correct
2	Correct	41 ms	117884 KB	Output is correct
3	Correct	39 ms	117840 KB	Output is correct
4	Correct	46 ms	117604 KB	Output is correct
5	Correct	41 ms	117844 KB	Output is correct
6	Correct	49 ms	117844 KB	Output is correct
7	Correct	53 ms	117840 KB	Output is correct
8	Correct	58 ms	117844 KB	Output is correct
9	Correct	44 ms	118096 KB	Output is correct
10	Correct	43 ms	117664 KB	Output is correct
11	Correct	45 ms	117672 KB	Output is correct
12	Correct	55 ms	117840 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	117720 KB	Output is correct
2	Correct	43 ms	117844 KB	Output is correct
3	Correct	45 ms	117708 KB	Output is correct
4	Correct	412 ms	128216 KB	Output is correct
5	Correct	300 ms	128164 KB	Output is correct
6	Correct	327 ms	125520 KB	Output is correct
7	Correct	364 ms	125264 KB	Output is correct
8	Correct	267 ms	124840 KB	Output is correct
9	Correct	375 ms	125520 KB	Output is correct
10	Correct	307 ms	125008 KB	Output is correct
11	Correct	42 ms	117748 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	117844 KB	Output is correct
2	Correct	46 ms	117852 KB	Output is correct
3	Correct	43 ms	117840 KB	Output is correct
4	Correct	44 ms	117836 KB	Output is correct
5	Correct	43 ms	117636 KB	Output is correct
6	Correct	44 ms	117848 KB	Output is correct
7	Correct	48 ms	117820 KB	Output is correct
8	Correct	44 ms	117748 KB	Output is correct
9	Correct	51 ms	117652 KB	Output is correct
10	Correct	42 ms	117840 KB	Output is correct
11	Correct	49 ms	117688 KB	Output is correct
12	Correct	610 ms	128888 KB	Output is correct
13	Correct	846 ms	123856 KB	Output is correct
14	Correct	193 ms	122952 KB	Output is correct
15	Correct	1066 ms	124752 KB	Output is correct
16	Correct	190 ms	127076 KB	Output is correct
17	Correct	517 ms	126292 KB	Output is correct
18	Correct	866 ms	128440 KB	Output is correct
19	Correct	691 ms	128592 KB	Output is correct
20	Correct	631 ms	127828 KB	Output is correct
21	Correct	44 ms	117844 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	117836 KB	Output is correct
2	Correct	45 ms	117840 KB	Output is correct
3	Correct	50 ms	117688 KB	Output is correct
4	Correct	57 ms	117656 KB	Output is correct
5	Correct	45 ms	117788 KB	Output is correct
6	Correct	43 ms	117796 KB	Output is correct
7	Correct	62 ms	117856 KB	Output is correct
8	Correct	53 ms	117840 KB	Output is correct
9	Correct	52 ms	117840 KB	Output is correct
10	Correct	42 ms	117788 KB	Output is correct
11	Correct	47 ms	117688 KB	Output is correct
12	Correct	371 ms	128340 KB	Output is correct
13	Correct	310 ms	128080 KB	Output is correct
14	Correct	314 ms	125448 KB	Output is correct
15	Correct	330 ms	125340 KB	Output is correct
16	Correct	290 ms	124756 KB	Output is correct
17	Correct	325 ms	125336 KB	Output is correct
18	Correct	317 ms	125296 KB	Output is correct
19	Correct	600 ms	129104 KB	Output is correct
20	Correct	896 ms	123708 KB	Output is correct
21	Correct	201 ms	122960 KB	Output is correct
22	Correct	986 ms	124752 KB	Output is correct
23	Correct	154 ms	127056 KB	Output is correct
24	Correct	539 ms	126288 KB	Output is correct
25	Correct	740 ms	128472 KB	Output is correct
26	Correct	685 ms	128608 KB	Output is correct
27	Correct	686 ms	128044 KB	Output is correct
28	Correct	447 ms	191432 KB	Output is correct
29	Correct	1266 ms	200260 KB	Output is correct
30	Correct	2663 ms	175844 KB	Output is correct
31	Correct	2445 ms	163972 KB	Output is correct
32	Correct	297 ms	127572 KB	Output is correct
33	Correct	452 ms	128144 KB	Output is correct
34	Correct	255 ms	193980 KB	Output is correct
35	Correct	874 ms	163412 KB	Output is correct
36	Correct	1676 ms	198024 KB	Output is correct
37	Correct	1287 ms	198308 KB	Output is correct
38	Correct	1217 ms	197716 KB	Output is correct
39	Correct	1158 ms	181828 KB	Output is correct
40	Correct	43 ms	117840 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	117848 KB	Output is correct
2	Correct	43 ms	117840 KB	Output is correct
3	Correct	44 ms	117840 KB	Output is correct
4	Correct	49 ms	117840 KB	Output is correct
5	Correct	47 ms	117788 KB	Output is correct
6	Correct	45 ms	117844 KB	Output is correct
7	Correct	44 ms	117844 KB	Output is correct
8	Correct	47 ms	117844 KB	Output is correct
9	Correct	45 ms	117844 KB	Output is correct
10	Correct	56 ms	117860 KB	Output is correct
11	Correct	43 ms	117852 KB	Output is correct
12	Correct	420 ms	128168 KB	Output is correct
13	Correct	324 ms	128084 KB	Output is correct
14	Correct	347 ms	125844 KB	Output is correct
15	Correct	373 ms	125264 KB	Output is correct
16	Correct	281 ms	124732 KB	Output is correct
17	Correct	372 ms	125268 KB	Output is correct
18	Correct	364 ms	124912 KB	Output is correct
19	Correct	649 ms	128852 KB	Output is correct
20	Correct	902 ms	123676 KB	Output is correct
21	Correct	221 ms	122960 KB	Output is correct
22	Correct	1041 ms	124928 KB	Output is correct
23	Correct	185 ms	127056 KB	Output is correct
24	Correct	560 ms	126368 KB	Output is correct
25	Correct	807 ms	128452 KB	Output is correct
26	Correct	754 ms	128424 KB	Output is correct
27	Correct	668 ms	127852 KB	Output is correct
28	Correct	554 ms	191520 KB	Output is correct
29	Correct	1335 ms	200068 KB	Output is correct
30	Correct	2636 ms	175796 KB	Output is correct
31	Correct	2638 ms	164060 KB	Output is correct
32	Correct	346 ms	127868 KB	Output is correct
33	Correct	456 ms	128084 KB	Output is correct
34	Correct	310 ms	194040 KB	Output is correct
35	Correct	849 ms	163332 KB	Output is correct
36	Correct	1746 ms	198044 KB	Output is correct
37	Correct	1352 ms	198168 KB	Output is correct
38	Correct	1459 ms	197708 KB	Output is correct
39	Runtime error	358 ms	256000 KB	Execution killed with signal 9
40	Halted	0 ms	0 KB	-