oj.uz

Submission #58484

# Submission time Handle Problem Language Result Execution time Memory
58484 2018-07-18T02:32:49 Z qkxwsm Game (IOI13_game) C++17
63 / 100
 6208 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];
	ll val;
	node()
	{
		val = 0;
		ch[0] = ch[1] = nullptr;
	}
};

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

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

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();
	}
	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[0] = upd(t -> ch[0], Lx, Rx, Ly, mid, x, y, v);
		t -> ch[1] = upd(t -> ch[1], Lx, Rx, mid + 1, Ry, x, y, v);
		t -> val = comb(getval(t -> ch[0]), getval(t -> ch[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[0], Lx, Rx, Ly, mid, x1, x2, y1, y2), query(t -> ch[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 5 ms 484 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 3 ms 748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 1560 ms 22264 KB Output is correct
5 Correct 979 ms 26344 KB Output is correct
6 Correct 1006 ms 28048 KB Output is correct
7 Correct 1263 ms 32512 KB Output is correct
8 Correct 743 ms 32512 KB Output is correct
9 Correct 1351 ms 41616 KB Output is correct
10 Correct 1312 ms 45832 KB Output is correct
11 Correct 2 ms 45832 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45832 KB Output is correct
2 Correct 4 ms 45832 KB Output is correct
3 Correct 5 ms 45832 KB Output is correct
4 Correct 3 ms 45832 KB Output is correct
5 Correct 3 ms 45832 KB Output is correct
6 Correct 5 ms 45832 KB Output is correct
7 Correct 3 ms 45832 KB Output is correct
8 Correct 4 ms 45832 KB Output is correct
9 Correct 4 ms 45832 KB Output is correct
10 Correct 4 ms 45832 KB Output is correct
11 Correct 3 ms 45832 KB Output is correct
12 Correct 2742 ms 60196 KB Output is correct
13 Correct 4434 ms 60196 KB Output is correct
14 Correct 991 ms 60196 KB Output is correct
15 Correct 5170 ms 63756 KB Output is correct
16 Correct 510 ms 82292 KB Output is correct
17 Correct 3043 ms 82292 KB Output is correct
18 Correct 5078 ms 92892 KB Output is correct
19 Correct 4724 ms 98420 KB Output is correct
20 Correct 4317 ms 103068 KB Output is correct
21 Correct 3 ms 103068 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 103068 KB Output is correct
2 Correct 5 ms 103068 KB Output is correct
3 Correct 6 ms 103068 KB Output is correct
4 Correct 3 ms 103068 KB Output is correct
5 Correct 2 ms 103068 KB Output is correct
6 Correct 5 ms 103068 KB Output is correct
7 Correct 3 ms 103068 KB Output is correct
8 Correct 4 ms 103068 KB Output is correct
9 Correct 5 ms 103068 KB Output is correct
10 Correct 3 ms 103068 KB Output is correct
11 Correct 3 ms 103068 KB Output is correct
12 Correct 1251 ms 103068 KB Output is correct
13 Correct 1000 ms 103068 KB Output is correct
14 Correct 1051 ms 103068 KB Output is correct
15 Correct 1203 ms 106060 KB Output is correct
16 Correct 724 ms 106060 KB Output is correct
17 Correct 1277 ms 115056 KB Output is correct
18 Correct 1162 ms 119356 KB Output is correct
19 Correct 3249 ms 133640 KB Output is correct
20 Correct 3949 ms 133640 KB Output is correct
21 Correct 971 ms 133640 KB Output is correct
22 Correct 5038 ms 137248 KB Output is correct
23 Correct 701 ms 155900 KB Output is correct
24 Correct 3044 ms 155900 KB Output is correct
25 Correct 5026 ms 166344 KB Output is correct
26 Correct 4356 ms 171868 KB Output is correct
27 Correct 4183 ms 176492 KB Output is correct
28 Runtime error 6208 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.
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 -