oj.uz

Submission #58485

# Submission time Handle Problem Language Result Execution time Memory
58485 2018-07-18T02:49:07 Z qkxwsm Game (IOI13_game) C++17
63 / 100
 6262 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 = new node();
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;
	}
	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 = r; M = c;
//	N = max(2, r);
//	M = max(2, c);
}

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 612 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 4 ms 680 KB Output is correct
5 Correct 3 ms 680 KB Output is correct
6 Correct 4 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 3 ms 696 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 2 ms 760 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1444 ms 22240 KB Output is correct
5 Correct 1144 ms 26416 KB Output is correct
6 Correct 1341 ms 28032 KB Output is correct
7 Correct 1212 ms 32464 KB Output is correct
8 Correct 746 ms 32464 KB Output is correct
9 Correct 1355 ms 41600 KB Output is correct
10 Correct 1152 ms 45784 KB Output is correct
11 Correct 3 ms 45784 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45784 KB Output is correct
2 Correct 5 ms 45784 KB Output is correct
3 Correct 5 ms 45784 KB Output is correct
4 Correct 4 ms 45784 KB Output is correct
5 Correct 4 ms 45784 KB Output is correct
6 Correct 5 ms 45784 KB Output is correct
7 Correct 3 ms 45784 KB Output is correct
8 Correct 3 ms 45784 KB Output is correct
9 Correct 5 ms 45784 KB Output is correct
10 Correct 4 ms 45784 KB Output is correct
11 Correct 3 ms 45784 KB Output is correct
12 Correct 2840 ms 60160 KB Output is correct
13 Correct 3912 ms 60160 KB Output is correct
14 Correct 777 ms 60160 KB Output is correct
15 Correct 4762 ms 63924 KB Output is correct
16 Correct 530 ms 82216 KB Output is correct
17 Correct 2666 ms 82216 KB Output is correct
18 Correct 4877 ms 92868 KB Output is correct
19 Correct 3846 ms 98352 KB Output is correct
20 Correct 3787 ms 103096 KB Output is correct
21 Correct 2 ms 103096 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 103096 KB Output is correct
2 Correct 4 ms 103096 KB Output is correct
3 Correct 5 ms 103096 KB Output is correct
4 Correct 3 ms 103096 KB Output is correct
5 Correct 2 ms 103096 KB Output is correct
6 Correct 5 ms 103096 KB Output is correct
7 Correct 3 ms 103096 KB Output is correct
8 Correct 3 ms 103096 KB Output is correct
9 Correct 4 ms 103096 KB Output is correct
10 Correct 3 ms 103096 KB Output is correct
11 Correct 4 ms 103096 KB Output is correct
12 Correct 1177 ms 103096 KB Output is correct
13 Correct 881 ms 103096 KB Output is correct
14 Correct 1223 ms 103096 KB Output is correct
15 Correct 1349 ms 106032 KB Output is correct
16 Correct 923 ms 106032 KB Output is correct
17 Correct 1170 ms 114948 KB Output is correct
18 Correct 1228 ms 119340 KB Output is correct
19 Correct 3137 ms 133492 KB Output is correct
20 Correct 4211 ms 133492 KB Output is correct
21 Correct 819 ms 133492 KB Output is correct
22 Correct 4798 ms 137232 KB Output is correct
23 Correct 500 ms 155928 KB Output is correct
24 Correct 2772 ms 155928 KB Output is correct
25 Correct 4826 ms 166432 KB Output is correct
26 Correct 4405 ms 171816 KB Output is correct
27 Correct 3856 ms 176568 KB Output is correct
28 Runtime error 6262 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 3 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 -