oj.uz

Submission #306448

# Submission time Handle Problem Language Result Execution time Memory
306448 2020-09-25T15:23:30 Z Temmie Game (IOI13_game) C++17
0 / 100
 13000 ms 6824 KB 
#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;
		ll r = 0;
		if (tl) r = gcd2(r, tl->get(xl, yl, xr, yr));
		if (tr) r = gcd2(r, tr->get(xl, yl, xr, yr));
		if (bl) r = gcd2(r, bl->get(xl, yl, xr, yr));
		if (br) r = gcd2(r, br->get(xl, yl, xr, yr));
		return r;
	}
	
};

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Execution timed out 13075 ms 6824 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -