oj.uz

Submission #650762

# Submission time Handle Problem Language Result Execution time Memory
650762 2022-10-15T09:25:02 Z ymm Game (IOI13_game) C++17
100 / 100
 4755 ms 147624 KB 
#include "game.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct node0 {
	ll x;
	int l, r;
} pool0[10000000];
struct node1 {
	int x;
	int l, r;
} pool1[10000000];
int new_node0(){static int nxt=1; return nxt++;}
int new_node1(){static int nxt=1; return nxt++;}

void up0(int p, ll x, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	if (e-b == 1) {
		t->x = x;
		return;
	}
	if (p < (b+e)/2) {
		if (!t->l) t->l = new_node0();
		up0(p, x, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node0();
		up0(p, x, t->r, (b+e)/2, e);
	}
	t->x = __gcd(t->l? pool0[t->l].x: 0, t->r? pool0[t->r].x: 0);
#undef t
}

void merge0(int p, int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	t->x = __gcd(l? pool0[l].x: 0, r? pool0[r].x: 0);
	if (e-b == 1)
		return;
	if (p < (b+e)/2) {
		if (!t->l) t->l = new_node0();
		merge0(p, l? pool0[l].l: 0, r? pool0[r].l: 0, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node0();
		merge0(p, l? pool0[l].r: 0, r? pool0[r].r: 0, t->r, (b+e)/2, e);
	}
#undef t
}

ll get0(int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	if (r <= b || e <= l || !t)
		return 0;
	if (l <= b && e <= r)
		return t->x;
	return __gcd(get0(l, r, t->l, b, (b+e)/2),
	             get0(l, r, t->r, (b+e)/2, e));
#undef t
}

int seg0_cpy(int t)
{
	if (!t)
		return 0;
#define t (pool0+t)
	int ans = new_node0();
	pool0[ans].x = t->x;
	pool0[ans].l = seg0_cpy(t->l);
	pool0[ans].r = seg0_cpy(t->r);
	return ans;
#undef t
}

void up1(int p1, int p0, ll x, int t, int b=0, int e=1e9)
{
#define t (pool1+t)
	if (e-b == 1) {
		if (!t->x) t->x = new_node0();
		up0(p0, x, t->x);
		return;
	}
	if (p1 < (b+e)/2) {
		if (!t->l) t->l = new_node1();
		up1(p1, p0, x, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node1();
		up1(p1, p0, x, t->r, (b+e)/2, e);
	}
	if (t->l && t->r) {
		if (!t->x) {
			int u = p1 < (b+e)/2? t->r: t->l;
			while (!pool1[u].x)
				u = pool1[u].l? pool1[u].l: pool1[u].r;
			t->x = seg0_cpy(pool1[u].x);
		}
		int ul = t->l, ur = t->r;
		while (!pool1[ul].x)
			ul = pool1[ul].l? pool1[ul].l: pool1[ul].r;
		while (!pool1[ur].x)
			ur = pool1[ur].l? pool1[ur].l: pool1[ur].r;
		merge0(p0, pool1[ul].x, pool1[ur].x, t->x);
	}
#undef t
}

ll get1(int l1, int r1, int l0, int r0, int t, int b=0, int e=1e9)
{
	if (r1 <= b || e <= l1 || !t)
		return 0;
#define t (pool1+t)
	if (l1 <= b && e <= r1) {
		if (!t->x) {
			if (t->l)
				return get1(l1,r1,l0,r0, t->l, b, (b+e)/2);
			else
				return get1(l1,r1,l0,r0, t->r, (b+e)/2, e);
		} else {
			return get0(l0, r0, t->x);
		}
	}
	return __gcd(get1(l1, r1, l0, r0, t->l, b, (b+e)/2),
	             get1(l1, r1, l0, r0, t->r, (b+e)/2, e));
#undef t
}

int rt = new_node1();

void init(int R, int C)
{
}

void update(int P, int Q, long long K)
{
	up1(P, Q, K, rt);
}

long long calculate(int P, int Q, int U, int V)
{
	int l1 = min(P, U);
	int r1 = max(P, U) + 1;
	int l0 = min(Q, V);
	int r0 = max(Q, V) + 1;
	return get1(l1, r1, l0, r0, rt);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 797 ms 8624 KB Output is correct
5 Correct 618 ms 8908 KB Output is correct
6 Correct 619 ms 5624 KB Output is correct
7 Correct 735 ms 5304 KB Output is correct
8 Correct 544 ms 4336 KB Output is correct
9 Correct 741 ms 5368 KB Output is correct
10 Correct 681 ms 5096 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 228 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1375 ms 10748 KB Output is correct
13 Correct 1602 ms 4368 KB Output is correct
14 Correct 661 ms 932 KB Output is correct
15 Correct 1874 ms 5880 KB Output is correct
16 Correct 568 ms 10940 KB Output is correct
17 Correct 1241 ms 7576 KB Output is correct
18 Correct 1608 ms 11328 KB Output is correct
19 Correct 1601 ms 11544 KB Output is correct
20 Correct 1351 ms 10688 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 757 ms 8648 KB Output is correct
13 Correct 637 ms 8956 KB Output is correct
14 Correct 633 ms 5556 KB Output is correct
15 Correct 707 ms 5356 KB Output is correct
16 Correct 534 ms 4304 KB Output is correct
17 Correct 646 ms 5464 KB Output is correct
18 Correct 622 ms 5160 KB Output is correct
19 Correct 1234 ms 10900 KB Output is correct
20 Correct 1547 ms 4260 KB Output is correct
21 Correct 632 ms 940 KB Output is correct
22 Correct 1878 ms 5848 KB Output is correct
23 Correct 576 ms 11016 KB Output is correct
24 Correct 1275 ms 7748 KB Output is correct
25 Correct 1810 ms 11164 KB Output is correct
26 Correct 1564 ms 11360 KB Output is correct
27 Correct 1457 ms 10764 KB Output is correct
28 Correct 1313 ms 47640 KB Output is correct
29 Correct 2480 ms 61940 KB Output is correct
30 Correct 4081 ms 39344 KB Output is correct
31 Correct 3936 ms 29876 KB Output is correct
32 Correct 930 ms 944 KB Output is correct
33 Correct 1202 ms 1376 KB Output is correct
34 Correct 239 ms 59076 KB Output is correct
35 Correct 1768 ms 28980 KB Output is correct
36 Correct 2662 ms 59520 KB Output is correct
37 Correct 2552 ms 59732 KB Output is correct
38 Correct 2419 ms 59104 KB Output is correct
39 Correct 2079 ms 44924 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 734 ms 8608 KB Output is correct
13 Correct 576 ms 8888 KB Output is correct
14 Correct 588 ms 5540 KB Output is correct
15 Correct 624 ms 5316 KB Output is correct
16 Correct 516 ms 4340 KB Output is correct
17 Correct 612 ms 5480 KB Output is correct
18 Correct 590 ms 5156 KB Output is correct
19 Correct 1207 ms 10928 KB Output is correct
20 Correct 1472 ms 4300 KB Output is correct
21 Correct 615 ms 1076 KB Output is correct
22 Correct 1722 ms 5760 KB Output is correct
23 Correct 524 ms 10828 KB Output is correct
24 Correct 1081 ms 7632 KB Output is correct
25 Correct 1534 ms 11408 KB Output is correct
26 Correct 1467 ms 11516 KB Output is correct
27 Correct 1390 ms 10728 KB Output is correct
28 Correct 1184 ms 47720 KB Output is correct
29 Correct 2424 ms 61948 KB Output is correct
30 Correct 3972 ms 39260 KB Output is correct
31 Correct 3804 ms 29820 KB Output is correct
32 Correct 879 ms 844 KB Output is correct
33 Correct 1195 ms 1468 KB Output is correct
34 Correct 251 ms 59036 KB Output is correct
35 Correct 1754 ms 28932 KB Output is correct
36 Correct 2786 ms 59560 KB Output is correct
37 Correct 2341 ms 59464 KB Output is correct
38 Correct 2243 ms 58848 KB Output is correct
39 Correct 1415 ms 115800 KB Output is correct
40 Correct 3246 ms 147624 KB Output is correct
41 Correct 4755 ms 95564 KB Output is correct
42 Correct 4575 ms 72548 KB Output is correct
43 Correct 415 ms 142232 KB Output is correct
44 Correct 832 ms 10620 KB Output is correct
45 Correct 2043 ms 55312 KB Output is correct
46 Correct 3225 ms 146276 KB Output is correct
47 Correct 2984 ms 146296 KB Output is correct
48 Correct 3144 ms 145860 KB Output is correct
49 Correct 1 ms 212 KB Output is correct