oj.uz

Submission #58467

# Submission time Handle Problem Language Result Execution time Memory
58467 2018-07-18T00:10:08 Z qkxwsm Game (IOI13_game) C++17
10 / 100
 1915 ms 257024 KB 
#include "game.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;
	}
};

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 (!t)
	{
		t = new node();
	}
	if (x < Lx || x > Rx || y < Ly || y > Ry)
	{
		return t;
	}
	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;
		return t;
	}
	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(t -> ch[1][0] -> val, t -> ch[1][1] -> val);
	}
	return t;
}

ll query(node *t, int Lx, int Rx, int Ly, int Ry, int x1, int x2, int y1, int y2)
{
	if (!t)
	{
		t = new node();
	}
	if (x2 < Lx || x1 > Rx || y2 < Ly || y1 > Ry)
	{
		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)
{
	upd(root, 0, N - 1, 0, M - 1, x, y, v);
}

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1036 KB Output is correct
2 Correct 2 ms 1036 KB Output is correct
3 Correct 3 ms 1036 KB Output is correct
4 Runtime error 1915 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.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 -

Subtask #4
0 / 17.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 -

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 -