Submission #411608

#	Time	Username	Problem	Language	Result	Execution time	Memory
411608		Mlxa	Game (IOI13_game)	C++14	0 / 100	5 ms	716 KiB

game

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"

ll gcd(ll x, ll y) {
	ll tmp;
	while (x != y && y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

const int NODES = 1e6;
const int RANGE = 1 << 30;

struct node {
	int ls;
	int rs;
	int tx;
	ll gc;
} pool[NODES];
int ff = 1;

#define gt(t,f) t &f(int v) { assert(0 <= v && v < ff); return pool[v].f; }
gt(int,ls) gt(int,rs) gt(int,tx) gt(ll,gc)

int new_node() {
	int v = ff++;
	ls(v) = rs(v) = tx(v) = 0;
	gc(v) = 0;
	return v;
}

void updatey(int &v, int vl, int vr, int q, ll d) {
	assert(vl <= q && q < vr);
	if (!v) {
		v = new_node();
	}
	if (vr - vl == 1) {
		gc(v) = d;
		return;
	}
	int vm = (vl + vr) / 2;
	if (q < vm) {
		updatey(ls(v), vl, vm, q, d);
	} else {
		updatey(rs(v), vm, vr, q, d);
	}
	gc(v) = gcd(gc(ls(v)), gc(rs(v)));
}

void updatex(int &v, int vxl, int vxr, int vyl, int vyr, int qx, int qy, ll d) {
	assert(vxl <= qx && qx < vxr);
	assert(vyl <= qy && qy < vyr);
	updatey(tx(v), vyl, vyr, qy, d);
	updatey(v, vyl, vyr, qy, d);
	if (vxr - vxl == 1) {
		return;
	}
	int vxm = (vxl + vxr) / 2;
	if (qx < vxm) {
		updatex(ls(v), vxl, vxm, vyl, vyr, qx, qy, d);
	} else {
		updatex(rs(v), vxm, vxr, vyl, vyr, qx, qy, d);
	}
}

ll queryy(int v, int vl, int vr, int ql, int qr) {
	if (!v || qr <= vl || vr <= ql) {
		return 0;
	}
	if (ql <= vl && vr <= qr) {
		return gc(v);
	}
	int vm = (vl + vr) / 2;
	return gcd(queryy(ls(v), vl, vm, ql, qr), queryy(rs(v), vm, vr, ql, qr));
}

ll queryx(int v, int vxl, int vxr, int vyl, int vyr, int qxl, int qxr, int qyl, int qyr) {
	if (!v || qxr <= vxl || vxr <= qxl) {
		return 0;
	}
	if (qxl <= vxl && vxr <= qxr) {
		return queryy(tx(v), vyl, vyr, qyl, qyr);
	}
	int vxm = (vxl + vxr) / 2;
	return gcd(queryx(ls(v), vxl, vxm, vyl, vyr, qxl, qxr, qyl, qyr), queryx(rs(v), vxm, vxr, vyl, vyr, qxl, qxr, qyl, qyr));
}

void init(int r, int c) {
	(void)r; (void)c;
}

int root = 0;

void update(int p, int q, ll k) {
	updatex(root, 0, RANGE, 0, RANGE, p, q, k);
}

ll calculate(int p, int q, int u, int v) {
	return queryx(root, 0, RANGE, 0, RANGE, p, u + 1, q, v + 1);
}

#ifdef LC
#include "grader.c"
#endif

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20