Submission #58484

#	Time	Username	Problem	Language	Result	Execution time	Memory
58484		qkxwsm	Game (IOI13_game)	C++17	63 / 100	6208 ms	257024 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20