Submission #1164064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164064		tesseract	Game (IOI13_game)	C++20	80 / 100	9337 ms	276512 KiB

game

#include "game.h"
#define NDEBUG
#include <cassert>
#include <forward_list>
#include <map>
//#include "ezprint.h"
#include <iostream>
#include <set>
#include <vector>

using namespace std;

enum class Dim {ROW, COL};



long long gcd2(long long X, long long Y);
template<class Key, class T, class Compare, class Allocator>
T getOrDefault(const map<Key, T, Compare, Allocator> &m, const Key &k, const T &def) {
	auto it = m.find(k);
	return it == m.end() ? def : it->second;
}

// Intended for nonempty intervals.
struct Interval {
	int L, U;

	inline bool operator==(const Interval &other) const = default;

	inline int length() const {return U-L;}

	inline bool contains(const Interval &x) const { return L <= x.L && x.U <= U; }
	inline bool contains(int x) const { return L <= x && x < U;}
	inline bool nonempty() const { return length() > 0; }
	inline int mid() const { return L + (U-L)/2;}
	inline Interval leftHalf() const { return Interval {L, mid()};}
	inline Interval rightHalf() const { return Interval {mid(), U};}
};

// Intended for intervals known to intersect.
inline Interval intersection(const Interval &x, const Interval &y) {
	return {max(x.L, y.L), min(x.U, y.U)};
}


inline bool intersects(const Interval &x, const Interval &y) {
	return intersection(x, y).nonempty();
}

template<Dim D>
struct PayloadType {
	using type = void;
};

template<Dim D>
class LazySegTree {
public:

	struct Node {
	private:
		Node *left, *right;

		// The uld (unique lowest descendant) of a node is defined as follows:
		// uld(n) =
		// if n has exactly 1 child, then uld(n's child)
		// else n
		//
		// The idea is that for segment tree purposes, uld(n) has the "equivalent content"
		// of n, and so can be used in place of n.
		Node *uld;

		Node() :  left(nullptr), right(nullptr), uld(nullptr) {}

		Node(const Node &) = delete;
		Node(Node &&) = delete;
		Node &operator=(const Node &) = delete;

		int nChildren() const { return (left ? 1 : 0) + (right ? 1 : 0);}
	public:
		Node *getL() const { return left ? left->uld : nullptr; }
		Node *getR() const { return right ? right->uld : nullptr; }

		PayloadType<D>::type payload;

		friend class LazySegTree;
	};

	struct NodePtrIvl {
		Node *node;
		Interval ivl;

		NodePtrIvl leftHalf() const { return {node->left, ivl.leftHalf()};}
		NodePtrIvl rightHalf() const { return {node->right, ivl.rightHalf()};}
	};
private:
	NodePtrIvl root;

	void decompose(const NodePtrIvl &nodePtrIvl, const Interval &queryIvl, forward_list<Node *> &ids) const {
		Node *node = nodePtrIvl.node;
		Interval nodeIvl = nodePtrIvl.ivl;

		assert(nodeIvl.contains(queryIvl));
		if(nodeIvl == queryIvl) {
			assert(node->uld);
			ids.push_front(node->uld);
			return;
		}
		auto leftIvl = nodeIvl.leftHalf();
		auto rightIvl = nodeIvl.rightHalf();
		if(node->left && intersects(leftIvl, queryIvl)) {
			decompose(nodePtrIvl.leftHalf(), intersection(leftIvl, queryIvl), ids);
		}
		if(node->right && intersects(rightIvl, queryIvl)) {
			decompose(nodePtrIvl.rightHalf(), intersection(rightIvl, queryIvl), ids);
		}
	}

	void printInternal(const NodePtrIvl &nodePtrIvl, int indent) {
		for(int i=0; i<2*indent; ++i) { cout << " ";}
		//ez::println("Node ", nodePtrIvl.node, " ivl ", nodePtrIvl.ivl, " uld ", nodePtrIvl.node->uld);
		if(nodePtrIvl.node->left) {
			for(int i=0; i<2*indent; ++i) { cout << " ";}
			//ez::println("left:");
			printInternal(nodePtrIvl.leftHalf(), indent+1);
		}
		if(nodePtrIvl.node->right) {
			for(int i=0; i<2*indent; ++i) { cout << " ";}
			//ez::println("right:");
			printInternal(nodePtrIvl.rightHalf(), indent+1);
		}
	}

public:

	inline LazySegTree(int N) : root(nullptr, {0,N}) {
		assert(N >= 1);
	}

	struct Updates {
		forward_list<Node *> nodes;
		Node *pivotOld;
		Node *pivotNew;
	};

	// Ensure that all nodes on the path from the root [0,N) to the
	// leaf [x, x+1) exist. Returns all "relevant" nodes on this path,
	// that is, those which don't have exactly one child.
	// The returned list has nodes in the order from leaf to root.
	Updates ensureNodesAndUpdates(int x) {
		if(!root.node) { root.node = new Node(); }

		assert(root.ivl.contains(x));

		forward_list<Node *> ids;


		NodePtrIvl cur = root;
		Node *pendingToAssignUld[34]; // Upper bound on height
		int pendingToAssignUldSize = 0;
		Node *pivotOld = nullptr, *pivotNew = nullptr;
		while(cur.node) {
			assert(cur.ivl.contains(x));
			pendingToAssignUld[pendingToAssignUldSize++] = cur.node;

			NodePtrIvl nextCur {nullptr, {0,0}};
			if(cur.ivl.length() > 1) {
				int mid = cur.ivl.mid();
				if(x < mid) {
					if (!cur.node->left) { cur.node->left = new Node(); }
					nextCur = cur.leftHalf();
				} else {
					if (!cur.node->right) { cur.node->right = new Node(); }
					nextCur = cur.rightHalf();
				}
			}

			if(cur.node->nChildren() == 2 && cur.node->uld != cur.node) {
				// cur.node is not a pivot, but is about to become one below.
				// cur.node->uld is a descendant of cur.node, and its information
				// in the segment tree must be carried over to cur.node.
				assert(!pivotOld); assert(!pivotNew);
				pivotOld = cur.node->uld;
				pivotNew = cur.node;
				assert(pivotOld); assert(pivotNew);
			}

			if(cur.node->nChildren() != 1) {
				for(int i=0; i<pendingToAssignUldSize; ++i) {
					pendingToAssignUld[i]->uld = cur.node;
				}
				pendingToAssignUldSize = 0;
				ids.push_front(cur.node);
			}
			cur = nextCur;
		}
		return {ids, pivotOld, pivotNew};
	}

	// Try to decompose [a,b) into constituent intervals as
	// if this was a full segtree. Let X be the set of values for
	// which createIntervalsAndGetIds has been called.
	// Consider the ids returned by this method, and
	// let Y be the union of their corresponding intervals.
	// Then we have Y intersection X = [a,b) intersection X.
	// If this was a full segtree, we would have Y = [a,b).
	// Of course, we also have that the size of the returned list
	// is at most logarithmic in N.
	forward_list<Node *> decomposeIntervalAndGetIds(const Interval &ivl) const {
		forward_list<Node *> ids;
		if(root.node) {
			decompose(root, ivl, ids);
		}
		return ids;
	}

	// void print() {
	// 	printInternal(root, 0);
	// }
};


template<> struct PayloadType<Dim::ROW> {
	using type=map<LazySegTree<Dim::COL>::Node *, long long>;
};

template<> struct PayloadType<Dim::COL> {
	using type=vector<LazySegTree<Dim::ROW>::Node *>;
};


LazySegTree<Dim::ROW> Rtree(1);
LazySegTree<Dim::COL> Ctree(1);

typedef LazySegTree<Dim::ROW>::Node * RNodeId;
typedef LazySegTree<Dim::COL>::Node * CNodeId;


inline long long getGcd(RNodeId r, CNodeId c) {
	return getOrDefault(r->payload, c, 0LL);
}

inline void setGcd(RNodeId r, CNodeId c, long long val) {
	auto [it, wasInserted] = r->payload.insert({c, val});
	it->second = val;
	if(wasInserted) {
		c->payload.push_back(r);
	}
}


void init(int R, int C) {
	Rtree = LazySegTree<Dim::ROW>(R);
	Ctree = LazySegTree<Dim::COL>(C);
}

void update(int P, int Q, long long K) {
	// Each of these is ordered from leaf to root.
	auto rUpdates = Rtree.ensureNodesAndUpdates(P);
	auto cUpdates = Ctree.ensureNodesAndUpdates(Q);

	// First we do some transformations on data structure which
	// keeps it equivalent, by adding the pivot nodes.
	//ez::println("\n\n\n\nupdate P=", P, " Q=", Q, " K=", K, "\nRtree");
	//Rtree.print();
	//ez::println("\nCtree");
	//Ctree.print();
	//ez::println();

	if(rUpdates.pivotOld) {
		assert(rUpdates.pivotNew);
		assert(rUpdates.pivotOld != rUpdates.pivotNew);
		assert(rUpdates.pivotNew->payload.empty());
		rUpdates.pivotNew->payload = rUpdates.pivotOld->payload;
		for(auto [c, _] : rUpdates.pivotOld->payload) {
			c->payload.push_back(rUpdates.pivotNew);
		}
	}
	if(cUpdates.pivotOld) {
		assert(cUpdates.pivotNew);
		assert(cUpdates.pivotOld != cUpdates.pivotNew);
		for(auto r : cUpdates.pivotOld->payload) {
			setGcd(r, cUpdates.pivotNew, getGcd(r, cUpdates.pivotOld));
		}
	}
	// The equivalent transformations are done, now we do
	// the actual insert


	forward_list<RNodeId> rIds = rUpdates.nodes;
	forward_list<CNodeId> cIds = cUpdates.nodes;

	assert(!rIds.empty());
	assert(!cIds.empty());

	//ez::println("rIds ", rIds);
	//ez::println("cIds ", cIds);

	for (auto rId : rIds)
	for (auto cId : cIds) {
		if (rId == rIds.front() && cId == cIds.front()) { // base case
			setGcd(rId, cId, K);
			continue;
		}
		// We have a rectangle which can be split in half in two ways
		// We can choose either arbitrarily, except for a 1xN or Nx1
		// rectangle, in which case there is only one choice.
		if (rId == rIds.front()) {
			// cId->getL or cId->getR() can be nullptr if that child doesn't exist (hasn't been populated)
			// in the tree. This is not a problem, since in that case that key doesn't exist
			// in the map, so 0 is returned, as desired.
			setGcd(rId, cId, gcd2(getGcd(rId, cId->getL()), getGcd(rId, cId->getR())));
		} else {
			setGcd(rId, cId, gcd2(getGcd(rId->getL(), cId), getGcd(rId->getR(), cId)));
		}
	}
	//ez::println("After update ", gcds);

}

long long calculate(int P, int Q, int U, int V) {
	auto rIds = Rtree.decomposeIntervalAndGetIds({P, U+1});
	auto cIds = Ctree.decomposeIntervalAndGetIds({Q, V+1});

	long long ans = 0;
	for(auto rId : rIds)
	for(auto cId : cIds) {
		ans = gcd2(ans, getGcd(rId, cId));
		if (ans==1) { return 1; }
	}
	return ans;
}




inline 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;
}

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