Submission #556180

#	Time	Username	Problem	Language	Result	Execution time	Memory
556180		Zanite	Game (IOI13_game)	C++17	100 / 100	2871 ms	78404 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long

long long gcd2(long long X, long long Y) {
    if (!X) return Y;
	if (!Y) return X;
	return gcd2(Y, X % Y);
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
	struct Node {
		ll val, g;
		ll prior, pos, mn, mx;
		Node *left, *right;

		Node(ll _pos, ll _val) {
			pos = mn = mx = _pos;
			val = g = _val;
			prior = rng();
			left = right = nullptr;
		}
		
		void update() {
			g = val;
			if (left) {g = gcd2(g, left->g);}
			if (right) {g = gcd2(g, right->g);}

			mn = (left ? left->mn : pos);
			mx = (right ? right->mx : pos);
		}
	};

	Node *root;

	Treap() : root(nullptr) {}

	void split(Node *T, Node *&L, Node *&R, ll sep) {
		// splits T into L = [mn..pos] and R = [pos+1..mx]
		if (!T) {
			L = R = nullptr;
			return;
		}

		if (T->pos <= sep) {
			split(T->right, T->right, R, sep);
			L = T;
		} else {
			split(T->left, L, T->left, sep);
			R = T;
		}

		T->update();
	}

	void merge(Node *&T, Node *L, Node *R) {
		// merges L and R into T, assuming that all elements in L < R
		if (!L || !R) {
			T = (L ? L : R);
			return;
		}

		if (L->prior >= R->prior) {
			merge(L->right, L->right, R);
			T = L;
		} else {
			merge(R->left, L, R->left);
			T = R;
		}

		T->update();
	}

	bool find(ll pos) {
		// returns TRUE if the node with position pos is present in the treap
		Node *cur = root;
		while (cur) {
			if (cur->pos == pos) {return true;}
			if (cur->pos < pos) {cur = cur->right;}
			else {cur = cur->left;}
		}
		return false;
	}

	void updateNode(Node *cur, ll pos, ll val) {
		// updates node at position pos with val, assuming the node exists
		if (cur->pos == pos) {
			cur->val = val;
			cur->update();
			return;
		}
		
		if (cur->pos < pos) {
			updateNode(cur->right, pos, val);
		} else {
			updateNode(cur->left, pos, val);
		}
		cur->update();
	}

	void update(ll pos, ll val) {
		// if the node exists, update it
		if (find(pos)) {updateNode(root, pos, val);}
		else {
			// insert a new node
			Node *tmp = new Node(pos, val);
			Node *t1, *t2;
			split(root, t1, t2, pos);
			merge(root, t1, tmp);
			merge(root, root, t2);
		}
	}

	ll query(Node *T, ll L, ll R) {
		// returns sum of all nodes in the range [L..R] under node T
		if (!T) return 0;
		if (T->mx < L || R < T->mn) return 0;
		if (L <= T->mn && T->mx <= R) {
			//cout << "{" << T->mn << ", " << T->mx << ": " << T->g << "} ";
			return T->g;
		}

		ll ret;
		if (L <= T->pos && T->pos <= R) {
			//cout << "{" << T->pos << ", " << T->pos << ": " << T->val << "} ";
			ret = T->val;
		} else {
			ret = 0;
		}
		if (T->left) {ret = gcd2(ret, query(T->left, L, R));}
		if (T->right) {ret = gcd2(ret, query(T->right, L, R));}
		return ret;
	}

	ll query(ll L, ll R) {
		// returns sum of all nodes in the range [L..R]
		return query(root, L, R);
	}

	void print(Node *T) {
		if (!T) return;
		cout << T->pos << ' ' << T->val << ' ' << T->g << ' ' << T->mn << ' ' << T->mx << '\n';
		print(T->left);
		print(T->right);
	}

	void print() {
		print(root);
	}
};

struct DynamicSegtreeBBST {
	struct Node {
		Treap inner;
		Node* left;
		Node* right;

		Node() {
			inner = Treap();
			left = right = nullptr;
		}

		void update(ll pos) {
			ll tmp = 0;
			if (left) {tmp = gcd(tmp, left->inner.query(pos, pos));}
			if (right) {tmp = gcd(tmp, right->inner.query(pos, pos));}
			inner.update(pos, tmp);
		}
	};

	Node* root;
	ll dim1, dim2;

	DynamicSegtreeBBST(ll _dim1, ll _dim2) {
		root = new Node();
		dim1 = _dim1, dim2 = _dim2;
	}

	void update(Node* cur, ll l, ll r, ll d1, ll d2, ll upd) {
		if (l == r) {
			cur->inner.update(d2, upd);
			return;
		}

		ll m = (l + r) >> 1;
		if (d1 <= m) {
			if (!cur->left) {cur->left = new Node();}
			update(cur->left, l, m, d1, d2, upd);
		} else {
			if (!cur->right) {cur->right = new Node();}
			update(cur->right, m+1, r, d1, d2, upd);
		}
		cur->update(d2);
	}

	ll query(Node* cur, ll l, ll r, ll d1l, ll d1r, ll d2l, ll d2r) {
		if (l > d1r || d1l > r) {return 0;}
		if (d1l <= l && r <= d1r) {
			//debug(l); debug(r);
			//cur->inner.print();
			//cout << "{" << l << ", " << r << "} : ";
			ll ret = cur->inner.query(d2l, d2r);
			//cout << ": " << ret << '\n';
			//debug(ret);
			return ret;
		}

		ll m = (l + r) >> 1, ret = 0;
		if (cur->left) {ret = gcd2(ret, query(cur->left, l, m, d1l, d1r, d2l, d2r));}
		if (cur->right) {ret = gcd2(ret, query(cur->right, m+1, r, d1l, d1r, d2l, d2r));}
		return ret;
	}

    void print() {
        for (ll i = 1; i <= dim1; i++) {
            for (ll j = 1; j <= dim2; j++) {
                cout << query(root, 1, dim1, i, i, j, j) << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
};

DynamicSegtreeBBST *D;
int R, C;

void init(int R, int C) {
    ::R = R;
    ::C = C;
    D = new DynamicSegtreeBBST(R, C);
}

void update(int P, int Q, long long K) {
    D->update(D->root, 1, R, P+1, Q+1, K);
    //D->print();
}

long long calculate(int P, int Q, int U, int V) {
    return D->query(D->root, 1, R, P+1, U+1, Q+1, V+1);
}

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