Submission #306607

#	Time	Username	Problem	Language	Result	Execution time	Memory
306607		Temmie	Game (IOI13_game)	C++17	10 / 100	13095 ms	29712 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 {
	
	ll va, in;
	
	Node* ln, * rn;
	
	Node(ll VAL = 0, ll IND = 0) : va(VAL), in(IND), ln(nullptr), rn(nullptr) { }
	
	~Node() {
		if (ln) delete(ln);
		if (rn) delete(rn);
	}
	
	void set(ll ind, ll val, ll l, ll r) {
		if (!(r - l - 1LL)) {
			va = val;
			return;
		}
		ll mid = (l + r) >> 1LL;
		if (ind < mid) {
			if (!ln) ln = new Node(0, in * 2LL + 1LL);
			ln->set(ind, val, l, mid);
		} else {
			if (!rn) rn = new Node(0, in * 2LL + 2LL);
			rn->set(ind, val, mid, r);
		}
		ll newv = 0;
		if (ln) newv = gcd2(newv, ln->va);
		if (rn) newv = gcd2(newv, rn->va);
		va = newv;
	}
	
	ll get(ll tl, ll tr, ll l, ll r) {
		if (l >= tr || r <= tl) return 0;
		if (l >= tl && r <= tr) return va;
		ll mid = (l + r) >> 1LL;
		ll re = 0;
		if (ln) re = gcd2(re, ln->get(tl, tr, l, mid));
		if (rn) re = gcd2(re, rn->get(tl, tr, mid, r));
		return re;
	}
	
};

struct SNode {
	
	ll in;
	
	Node* node;
	
	SNode* ln, * rn;
	
	SNode(ll IND = 0) : in(IND), node(new Node), ln(nullptr), rn(nullptr) { }
	
	~SNode() {
		if (node) delete(node);
		if (ln) delete(ln);
		if (rn) delete(rn);
	}
	
	void merge(Node* l, Node* r, Node* t) {
		if (!l && !r) return;
		ll vl = 0;
		if (l) vl = gcd2(vl, l->va);
		if (r) vl = gcd2(vl, r->va);
		t->va = vl;
		if ((l && l->ln) || (r && r->ln)) {
			if (!t->ln) t->ln = new Node(0, t->in * 2LL + 1LL);
			merge(l ? l->ln : nullptr, r ? r->ln : nullptr, t->ln);
		}
		if ((l && l->rn) || (r && r->rn)) {
			if (!t->rn) t->rn = new Node(0, t->in * 2LL + 2LL);
			merge(l ? l->rn : nullptr, r ? r->rn : nullptr, t->rn);
		}
	}
	
	void set(ll ind, ll nind, ll val, ll l, ll r) {
		if (!(r - l - 1LL)) {
			node->set(nind, val, 0, size);
			return;
		}
		ll mid = (l + r) >> 1LL;
		if(ind < mid) {
			if (!ln) ln = new SNode(in * 2LL + 1LL);
			ln->set(ind, nind, val, l, mid);
		} else {
			if (!rn) rn = new SNode(in * 2LL + 2LL);
			rn->set(ind, nind, val, mid, r);
		}
		merge(ln ? ln->node : nullptr, rn ? rn->node : nullptr, node);
	}
	
	ll get(ll tl, ll tr, ll ntl, ll ntr, ll l, ll r) {
		if (l >= tr || r <= tl) return 0;
		if (l >= tl && r <= tr) return node->get(ntl, ntr, 0, size);
		ll mid = (l + r) >> 1LL;
		ll re = 0;
		if (ln) re = gcd2(re, ln->get(tl, tr, ntl, ntr, l, mid));
		if (rn) re = gcd2(re, rn->get(tl, tr, ntl, ntr, mid, r));
		return re;
	}
	
};

SNode* head = new SNode;

void init(int r, int c) { /* imagine needing it */ }

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

ll calculate(int r1, int c1, int r2, int c2) { return head->get(r1, r2 + 1, c1, c2 + 1, 0, size); }

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