Submission #306441

#	Time	Username	Problem	Language	Result	Execution time	Memory
306441		Temmie	Game (IOI13_game)	C++17	0 / 100	1 ms	384 KiB

game

#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

const ll size = 1073741824;

// ew begin //
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
// ew end //

struct Node {
	
	Node* tl, * tr, * bl, * br;
	
	ll topLx, topLy, recSize;
	
	ll valu;
	
	Node(ll X, ll Y, ll recsize) :
	tl(nullptr), tr(nullptr), bl(nullptr), br(nullptr),
	topLx(X), topLy(Y), recSize(recsize),
	valu(0)
	{ }
	
	~Node() {
		if (tl) delete(tl);
		if (tl) delete(tr);
		if (bl) delete(bl);
		if (br) delete(br);
	}
	
	void update(ll x, ll y, ll val) {
		if (x < topLx || x >= topLx + recSize || y < topLy || y >= topLy + recSize) return;
		if (recSize == 1LL) { valu = val; return; }
		ll xmid = (recSize + topLx + topLx) >> 1LL;
		ll ymid = (recSize + topLy + topLy) >> 1LL;
		if (!tl) tl = new Node(topLx, topLy, recSize >> 1LL);
		if (!bl) bl = new Node(topLx, ymid, recSize >> 1LL);
		if (!tr) tr = new Node(xmid, topLy, recSize >> 1LL);
		if (!br) br = new Node(xmid, ymid, recSize >> 1LL);
		tl->update(x, y, val);
		bl->update(x, y, val);
		tr->update(x, y, val);
		br->update(x, y, val);
		valu = gcd2(tl->valu, gcd2(tr->valu, gcd2(bl->valu, br->valu)));
	}
	
	ll get(ll xl, ll yl, ll xr, ll yr) {
		if (xr <= topLx || xl >= topLx + recSize || yr <= topLy || yl >= topLx + recSize) return 0;
		if (xl <= topLx && xr >= topLx + recSize && yl <= topLy && yr >= topLy + recSize) return valu;
		return gcd2(tl->get(xl, yl, xr, yr), gcd2(tr->get(xl, yl, xr, yr), gcd2(bl->get(xl, yl, xr, yr), br->get(xl, yl, xr, yr))));
	}
	
};

Node* head = nullptr;

void init(int r, int c) { head = new Node(0, 0, size); }

void update(int r, int c, ll val) { head->update(c, r, val); }

ll calculate(int tr, int tl, int br, int bl) { return head->get(tl, tr, bl + 1, br + 1); }

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