oj.uz

Submission #58475

# Submission time Handle Problem Language Result Execution time Memory
58475 2018-07-18T00:37:48 Z qkxwsm Game (IOI13_game) C++17
63 / 100
 4328 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;
int flag = 0;

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> mp;

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;
		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(mp[MP(Ly, MP(Lx, mid))], mp[MP(Ly, MP(mid + 1, Rx))]);
		}
		mp[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]));
	}
//	flag++;
	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(t -> ch[0][0], Lx, mid, Ly, Ry, x1, x2, y1, y2), query(t -> ch[0][1], 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)
{
//	flag = 0;
	upd(root, 0, N - 1, 0, M - 1, x, y, v);
//	cerr << flag << endl;
}

long long 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 376 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 808 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 808 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 2 ms 808 KB Output is correct
8 Correct 2 ms 808 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 2 ms 828 KB Output is correct
11 Correct 3 ms 828 KB Output is correct
12 Correct 2 ms 828 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 828 KB Output is correct
2 Correct 2 ms 828 KB Output is correct
3 Correct 2 ms 828 KB Output is correct
4 Correct 1500 ms 26452 KB Output is correct
5 Correct 794 ms 30532 KB Output is correct
6 Correct 990 ms 32384 KB Output is correct
7 Correct 1114 ms 36700 KB Output is correct
8 Correct 669 ms 36700 KB Output is correct
9 Correct 1056 ms 45612 KB Output is correct
10 Correct 1643 ms 49840 KB Output is correct
11 Correct 2 ms 49840 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49840 KB Output is correct
2 Correct 4 ms 49840 KB Output is correct
3 Correct 4 ms 49840 KB Output is correct
4 Correct 2 ms 49840 KB Output is correct
5 Correct 2 ms 49840 KB Output is correct
6 Correct 3 ms 49840 KB Output is correct
7 Correct 2 ms 49840 KB Output is correct
8 Correct 2 ms 49840 KB Output is correct
9 Correct 3 ms 49840 KB Output is correct
10 Correct 3 ms 49840 KB Output is correct
11 Correct 2 ms 49840 KB Output is correct
12 Correct 2091 ms 65776 KB Output is correct
13 Correct 3338 ms 65776 KB Output is correct
14 Correct 494 ms 65776 KB Output is correct
15 Correct 3882 ms 67368 KB Output is correct
16 Correct 442 ms 90504 KB Output is correct
17 Correct 1908 ms 90504 KB Output is correct
18 Correct 3059 ms 101156 KB Output is correct
19 Correct 2608 ms 106632 KB Output is correct
20 Correct 2566 ms 111340 KB Output is correct
21 Correct 2 ms 111340 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 111340 KB Output is correct
2 Correct 3 ms 111340 KB Output is correct
3 Correct 3 ms 111340 KB Output is correct
4 Correct 2 ms 111340 KB Output is correct
5 Correct 2 ms 111340 KB Output is correct
6 Correct 3 ms 111340 KB Output is correct
7 Correct 2 ms 111340 KB Output is correct
8 Correct 2 ms 111340 KB Output is correct
9 Correct 3 ms 111340 KB Output is correct
10 Correct 2 ms 111340 KB Output is correct
11 Correct 3 ms 111340 KB Output is correct
12 Correct 1136 ms 111340 KB Output is correct
13 Correct 809 ms 111340 KB Output is correct
14 Correct 1006 ms 111340 KB Output is correct
15 Correct 1259 ms 111340 KB Output is correct
16 Correct 794 ms 111340 KB Output is correct
17 Correct 1222 ms 119240 KB Output is correct
18 Correct 1118 ms 123692 KB Output is correct
19 Correct 2045 ms 139212 KB Output is correct
20 Correct 3383 ms 139212 KB Output is correct
21 Correct 489 ms 139212 KB Output is correct
22 Correct 4065 ms 140744 KB Output is correct
23 Correct 450 ms 164156 KB Output is correct
24 Correct 2131 ms 164156 KB Output is correct
25 Correct 3519 ms 174668 KB Output is correct
26 Correct 2969 ms 180116 KB Output is correct
27 Correct 3001 ms 184676 KB Output is correct
28 Runtime error 4328 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 -