oj.uz

Submission #390311

# Submission time Handle Problem Language Result Execution time Memory
390311 2021-04-15T19:57:51 Z rainboy Game (IOI13_game) C
100 / 100
 4283 ms 39064 KB 
#include "game.h"

#define LG	30	/* LG = ceil(log2(10^9)) */
#define NU	22000
#define N	(NU * (LG + 1))

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

int zz[1 + N], ll[1 + N], rr[1 + N], jj[1 + N], u_, l_, r_; long long xx[1 + N], yy[1 + N];

int node(int j) {
	static int _ = 1;

	zz[_] = rand_();
	jj[_] = j;
	return _++;
}

void pul(int u) {
	yy[u] = gcd(xx[u], gcd(yy[ll[u]], yy[rr[u]]));
}

void split(int u, int j) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (jj[u] < j) {
		split(rr[u], j);
		rr[u] = l_, l_ = u;
	} else if (jj[u] > j) {
		split(ll[u], j);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int uu[1 + N], ll_[1 + N], rr_[1 + N], t_, __ = 1, r, c;

void init(int R, int C) {
	r = R, c = C;
}

int update2(int u, int j, long long x) {
	split(u, j);
	if (u_ == 0)
		u_ = node(j);
	xx[u_] = yy[u_] = x;
	return merge(merge(l_, u_), r_);
}

long long get(long long u, int j) {
	while (u)
		if (jj[u] < j)
			u = rr[u];
		else if (jj[u] > j)
			u = ll[u];
		else
			return xx[u];
	return 0;
}

int update1(int t, int il, int ir, int i, int j, long long x) {
	if (t == 0)
		t = __++;
	if (ir - il > 1) {
		int im = (il + ir) / 2;

		if (i < im)
			ll_[t] = update1(ll_[t], il, im, i, j, x);
		else
			rr_[t] = update1(rr_[t], im, ir, i, j, x);
		x = gcd(get(uu[ll_[t]], j), get(uu[rr_[t]], j));
	}
	uu[t] = update2(uu[t], j, x);
	return t;
}

long long ans;

void query2(int u, int j1, int j2, int type) {
	if (u == 0)
		return;
	if (type == 0) {
		if (j2 <= jj[u])
			query2(ll[u], j1, j2, 0);
		else if (j1 > jj[u])
			query2(rr[u], j1, j2, 0);
		else {
			ans = gcd(ans, xx[u]);
			query2(ll[u], j1, j2, 1), query2(rr[u], j1, j2, -1);
		}
	} else if (type == -1) {
		if (j2 <= jj[u])
			query2(ll[u], j1, j2, -1);
		else {
			ans = gcd(gcd(ans, yy[ll[u]]), xx[u]);
			query2(rr[u], j1, j2, -1);
		}
	} else if (type == 1) {
		if (j1 > jj[u])
			query2(rr[u], j1, j2, 1);
		else {
			ans = gcd(gcd(ans, yy[rr[u]]), xx[u]);
			query2(ll[u], j1, j2, 1);
		}
	}
}

void query1(int t, int il, int ir, int i1, int i2, int j1, int j2) {
	int im;

	if (i2 <= il || ir <= i1 || uu[t] == 0)
		return;
	if (i1 <= il && ir <= i2) {
		query2(uu[t], j1, j2, 0);
		return;
	}
	im = (il + ir) / 2;
	query1(ll_[t], il, im, i1, i2, j1, j2);
	query1(rr_[t], im, ir, i1, i2, j1, j2);
}

void update(int i, int j, long long x) {
	t_ = update1(t_, 0, r, i, j, x);
}

long long calculate(int i1, int j1, int i2, int j2) {
	i2++, j2++;
	ans = 0, query1(t_, 0, r, i1, i2, j1, j2);
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 268 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 574 ms 10172 KB Output is correct
5 Correct 393 ms 9844 KB Output is correct
6 Correct 456 ms 7452 KB Output is correct
7 Correct 504 ms 7172 KB Output is correct
8 Correct 339 ms 6944 KB Output is correct
9 Correct 493 ms 7216 KB Output is correct
10 Correct 500 ms 6724 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 962 ms 9340 KB Output is correct
13 Correct 1409 ms 6288 KB Output is correct
14 Correct 339 ms 5572 KB Output is correct
15 Correct 1493 ms 7300 KB Output is correct
16 Correct 311 ms 8296 KB Output is correct
17 Correct 644 ms 8004 KB Output is correct
18 Correct 1086 ms 9728 KB Output is correct
19 Correct 938 ms 9936 KB Output is correct
20 Correct 892 ms 9300 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 579 ms 10004 KB Output is correct
13 Correct 400 ms 9908 KB Output is correct
14 Correct 462 ms 7364 KB Output is correct
15 Correct 526 ms 7048 KB Output is correct
16 Correct 338 ms 6832 KB Output is correct
17 Correct 495 ms 7108 KB Output is correct
18 Correct 509 ms 6820 KB Output is correct
19 Correct 961 ms 10892 KB Output is correct
20 Correct 1369 ms 6324 KB Output is correct
21 Correct 290 ms 5576 KB Output is correct
22 Correct 1497 ms 7412 KB Output is correct
23 Correct 316 ms 8388 KB Output is correct
24 Correct 639 ms 8080 KB Output is correct
25 Correct 1068 ms 9852 KB Output is correct
26 Correct 960 ms 9988 KB Output is correct
27 Correct 894 ms 9284 KB Output is correct
28 Correct 591 ms 23152 KB Output is correct
29 Correct 1549 ms 25812 KB Output is correct
30 Correct 2272 ms 17628 KB Output is correct
31 Correct 2058 ms 15388 KB Output is correct
32 Correct 410 ms 10248 KB Output is correct
33 Correct 560 ms 10260 KB Output is correct
34 Correct 506 ms 19568 KB Output is correct
35 Correct 826 ms 17164 KB Output is correct
36 Correct 1844 ms 23080 KB Output is correct
37 Correct 1407 ms 23380 KB Output is correct
38 Correct 1381 ms 22440 KB Output is correct
39 Correct 1101 ms 20388 KB Output is correct
40 Correct 1 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 619 ms 10152 KB Output is correct
13 Correct 447 ms 9908 KB Output is correct
14 Correct 451 ms 7312 KB Output is correct
15 Correct 564 ms 7184 KB Output is correct
16 Correct 348 ms 6720 KB Output is correct
17 Correct 498 ms 7216 KB Output is correct
18 Correct 518 ms 6852 KB Output is correct
19 Correct 978 ms 10920 KB Output is correct
20 Correct 1375 ms 6228 KB Output is correct
21 Correct 293 ms 5516 KB Output is correct
22 Correct 1610 ms 7180 KB Output is correct
23 Correct 345 ms 8216 KB Output is correct
24 Correct 653 ms 7980 KB Output is correct
25 Correct 1194 ms 9696 KB Output is correct
26 Correct 960 ms 9772 KB Output is correct
27 Correct 925 ms 9220 KB Output is correct
28 Correct 644 ms 21324 KB Output is correct
29 Correct 1592 ms 24008 KB Output is correct
30 Correct 2437 ms 17660 KB Output is correct
31 Correct 2115 ms 15296 KB Output is correct
32 Correct 418 ms 9224 KB Output is correct
33 Correct 536 ms 9644 KB Output is correct
34 Correct 555 ms 19556 KB Output is correct
35 Correct 847 ms 15600 KB Output is correct
36 Correct 2204 ms 20676 KB Output is correct
37 Correct 1663 ms 20788 KB Output is correct
38 Correct 1634 ms 20004 KB Output is correct
39 Correct 1061 ms 37252 KB Output is correct
40 Correct 3479 ms 39064 KB Output is correct
41 Correct 4283 ms 29396 KB Output is correct
42 Correct 3752 ms 24128 KB Output is correct
43 Correct 1012 ms 33864 KB Output is correct
44 Correct 575 ms 10528 KB Output is correct
45 Correct 1151 ms 20828 KB Output is correct
46 Correct 3103 ms 37940 KB Output is correct
47 Correct 3531 ms 37876 KB Output is correct
48 Correct 3406 ms 37548 KB Output is correct
49 Correct 1 ms 332 KB Output is correct