oj.uz

Submission #58483

# Submission time Handle Problem Language Result Execution time Memory
58483 2018-07-18T02:29:06 Z qkxwsm Game (IOI13_game) C++17
63 / 100
 8255 ms 257024 KB 
#include "game.h"
//#include "grader.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define y1 ___y1
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

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

ll comb(ll a, ll b)
{
	return (b == 0 ? a : comb(b, a % b));
}

int N, M;

struct node
{
	node *ch[2][2];
	ll val;
	node()
	{
		val = 0;
		ch[0][0] = ch[0][1] = nullptr;
		ch[1][0] = ch[1][1] = nullptr;
	}
};

ll getval(node *t)
{
	return (t ? t -> val : 0);
}

node *root;
map<pair<int, pii>, ll> mpchild;
map<pii, node*> mphead;
int creationz;

node* upd(node *t, int Lx, int Rx, int Ly, int Ry, int x, int y, ll v)
{
	if (x < Lx || x > Rx || y < Ly || y > Ry)
	{
		return t;
	}
	if (!t)
	{
		t = new node();
		creationz++;
	}
	if (Ly == 0 && Ry == M - 1 && Lx != Rx)
	{
		int mid = (Lx + Rx) / 2;
		node *lchild = mphead[MP(Lx, mid)], *rchild = mphead[MP(mid + 1, Rx)];
		if (!lchild) lchild = new node();
		if (!rchild) rchild = new node();
		lchild = upd(lchild, Lx, mid, Ly, Ry, x, y, v);
		rchild = upd(rchild, mid + 1, Rx, Ly, Ry, x, y, v);
		mphead[MP(Lx, mid)] = lchild;
		mphead[MP(mid + 1, Rx)] = rchild;
//		t -> ch[0][0] = upd(t -> ch[0][0], Lx, mid, Ly, Ry, x, y, v);
//		t -> ch[0][1] = upd(t -> ch[0][1], mid + 1, Rx, Ly, Ry, x, y, v);
	}
	if (Ly == Ry)
	{
		if (Lx == Rx)
		{
			t -> val = v;
		}
		else
		{
			int mid = (Lx + Rx) / 2;
			t -> val = comb(mpchild[MP(Ly, MP(Lx, mid))], mpchild[MP(Ly, MP(mid + 1, Rx))]);
		}
		mpchild[MP(Ly, MP(Lx, Rx))] = t -> val;
	}
	else
	{
		int mid = (Ly + Ry) / 2;
		t -> ch[1][0] = upd(t -> ch[1][0], Lx, Rx, Ly, mid, x, y, v);
		t -> ch[1][1] = upd(t -> ch[1][1], Lx, Rx, mid + 1, Ry, x, y, v);
		t -> val = comb(getval(t -> ch[1][0]), getval(t -> ch[1][1]));
	}
	return t;
}

ll query(node *t, int Lx, int Rx, int Ly, int Ry, int x1, int x2, int y1, int y2)
{
	if (x2 < Lx || x1 > Rx || y2 < Ly || y1 > Ry)
	{
		return 0;
	}
	if (!t)
	{
		return 0;
	}
	if (x1 <= Lx && Rx <= x2)
	{
		if (y1 <= Ly && Ry <= y2)
		{
			return t -> val;
		}
		int mid = (Ly + Ry) / 2;
		return comb(query(t -> ch[1][0], Lx, Rx, Ly, mid, x1, x2, y1, y2), query(t -> ch[1][1], Lx, Rx, mid + 1, Ry, x1, x2, y1, y2));
	}
	int mid = (Lx + Rx) / 2;
	return comb(query(mphead[MP(Lx, mid)], Lx, mid, Ly, Ry, x1, x2, y1, y2), query(mphead[MP(mid + 1, Rx)], mid + 1, Rx, Ly, Ry, x1, x2, y1, y2));
}

void init(int r, int c)
{
	N = max(2, r);
	M = max(2, c);
	root = new node();
}

void update(int x, int y, ll v)
{
	upd(root, 0, N - 1, 0, M - 1, x, y, v);
}

ll calculate(int x1, int y1, int x2, int y2)
{
	return query(root, 0, N - 1, 0, M - 1, x1, x2, y1, y2);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 4 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 4 ms 932 KB Output is correct
10 Correct 3 ms 932 KB Output is correct
11 Correct 4 ms 932 KB Output is correct
12 Correct 3 ms 932 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 932 KB Output is correct
2 Correct 3 ms 932 KB Output is correct
3 Correct 2 ms 932 KB Output is correct
4 Correct 1345 ms 26432 KB Output is correct
5 Correct 970 ms 30600 KB Output is correct
6 Correct 1266 ms 32328 KB Output is correct
7 Correct 1420 ms 36708 KB Output is correct
8 Correct 750 ms 36708 KB Output is correct
9 Correct 1285 ms 45716 KB Output is correct
10 Correct 1043 ms 50016 KB Output is correct
11 Correct 3 ms 50016 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 50016 KB Output is correct
2 Correct 5 ms 50016 KB Output is correct
3 Correct 4 ms 50016 KB Output is correct
4 Correct 2 ms 50016 KB Output is correct
5 Correct 3 ms 50016 KB Output is correct
6 Correct 5 ms 50016 KB Output is correct
7 Correct 3 ms 50016 KB Output is correct
8 Correct 4 ms 50016 KB Output is correct
9 Correct 6 ms 50016 KB Output is correct
10 Correct 4 ms 50016 KB Output is correct
11 Correct 4 ms 50016 KB Output is correct
12 Correct 3034 ms 66004 KB Output is correct
13 Correct 3832 ms 66004 KB Output is correct
14 Correct 852 ms 66004 KB Output is correct
15 Correct 4872 ms 67740 KB Output is correct
16 Correct 511 ms 91096 KB Output is correct
17 Correct 2871 ms 91096 KB Output is correct
18 Correct 5091 ms 101480 KB Output is correct
19 Correct 3943 ms 107004 KB Output is correct
20 Correct 4226 ms 111600 KB Output is correct
21 Correct 3 ms 111600 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 111600 KB Output is correct
2 Correct 4 ms 111600 KB Output is correct
3 Correct 5 ms 111600 KB Output is correct
4 Correct 3 ms 111600 KB Output is correct
5 Correct 2 ms 111600 KB Output is correct
6 Correct 4 ms 111600 KB Output is correct
7 Correct 2 ms 111600 KB Output is correct
8 Correct 3 ms 111600 KB Output is correct
9 Correct 4 ms 111600 KB Output is correct
10 Correct 4 ms 111600 KB Output is correct
11 Correct 4 ms 111600 KB Output is correct
12 Correct 1421 ms 111600 KB Output is correct
13 Correct 1002 ms 111600 KB Output is correct
14 Correct 1119 ms 111600 KB Output is correct
15 Correct 1392 ms 111600 KB Output is correct
16 Correct 779 ms 111600 KB Output is correct
17 Correct 1379 ms 119184 KB Output is correct
18 Correct 1655 ms 123604 KB Output is correct
19 Correct 2937 ms 139240 KB Output is correct
20 Correct 3991 ms 139240 KB Output is correct
21 Correct 968 ms 139240 KB Output is correct
22 Correct 5415 ms 141172 KB Output is correct
23 Correct 566 ms 164388 KB Output is correct
24 Correct 3403 ms 164388 KB Output is correct
25 Correct 5336 ms 174932 KB Output is correct
26 Correct 4685 ms 180480 KB Output is correct
27 Correct 4578 ms 185032 KB Output is correct
28 Execution timed out 8255 ms 257024 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -