Submission #1156882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156882		tesseract	Game (IOI13_game)	C++20	63 / 100	13093 ms	217028 KiB

game

constexpr int BR = 3;
/* Here we use a segment tree with a branching factor of BR which
 * could be more than the standard 2. If a node represents an interval
 * of length T, its chilren are defined as follows: If T is 1, this
 * is a leaf node with no children. Otherwise, it has up to BR children,
 * as follows. Let's start with exactly BR childre, with every child
 * having T/BR or T/BR + 1 elements. The leftmost T%BR children have
 * T/BR + 1 elements, and the remaining have T/BR elements.
 * The leftmost T%BR children contribute T%BR * (T/BR + 1) elements.
 * The remaining BR - T%BR children contribute (BR - T%BR) * (T/BR)
 * elements. Adding the two, we get
 * T%BR * (T/BR + 1) + (BR - T%BR) * (T/BR)
 * = T%BR * T/BR  +  T%BR  +  BR * T/BR  -  T%BR * T/BR
 * = BR * T/BR  +  T%BR
 * = T
 * as expected.
 *
 * Finally, any nodes with zero elements are deleted.
 */



#include "game.h"
#include <cassert>
#include <vector>
#include <map>
#include <ranges>

using namespace std;
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 vector<Interval> children() const {
		int T = length();
		if (T == 1) {
			return vector<Interval>();
		}
		vector<Interval> ans;


		int x = L;
		for(auto _ : views::iota(0, T%BR)) {
			ans.push_back({x, x + T/BR + 1});
			x += T/BR + 1;
		}
		if (T/BR != 0) {
			for(auto _ : views::iota(T%BR, BR)) {
				ans.push_back({x, x + T/BR});
				x += T/BR;
			}
		}
		//DELETEMEassert(x == U);
		return ans;
	}

	// returns whichth child of this node x belongs to.
	inline int getChildIndex(int x) const {
		//DELETEMEassert(contains(x));
		int T = length();

		// This interval is divided into BR intervals:
		// 1. First T%BR have length T/BR + 1
		// 2. Remaining have length T/BR

		// y is position relative to the beginning of this interval.
		int y = x - L;
		// Is x in the first T%BR children?
		int ans;
		if(y < (T%BR) * (T/BR + 1)) {
			ans = y/(T/BR + 1);
		} else {
			// z is position relative to the beginning of the second set of child intervals.
			int z = y - (T%BR) * (T/BR + 1);
			ans = T%BR + z/(T/BR);
		}
		//DELETEMEassert(0 <= ans);
		//DELETEMEassert(ans < BR);
		//DELETEMEassert(children().at(ans).contains(x));
		return ans;
	}
};

// 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();
}


class LazySegTreeIntervals {
private:
	int nextId = 0;

	struct Node {
		int id;
		// We can avoid having Interval here, but not clear if this optimization is useful.
		//Interval ivl;
		Node *children[BR];

		Node(int id_) : id(id_)  { fill(children, children + BR, nullptr);}
	};

	// The interval must correspond to the node.
	struct NodePtrIvl {
		Node *node;
		Interval ivl;

		inline vector<NodePtrIvl> children() const {
			vector<Interval> c = ivl.children();
			vector<NodePtrIvl> ans;
			ans.reserve(c.size());

			for(int i=0; i<c.size(); ++i) {
				ans.emplace_back(node->children[i], c[i]);
			}
			return ans;
		}
	};

	NodePtrIvl root;


	inline Node *createNewNode() {
		return new Node(nextId++);
	}

	void decompose(const NodePtrIvl &n, const Interval &queryIvl, vector<int> &ids) const {
		//DELETEMEassert(n.ivl.contains(queryIvl));
		if(n.ivl == queryIvl) {
			ids.push_back(n.node->id);
			return;
		}
		for(auto child : n.children()) {
			if(child.node && intersects(child.ivl, queryIvl)) {
				decompose(child, intersection(child.ivl, queryIvl), ids);
			}
		}
	}


public:

	struct ParentChildIds {
		int p;
		int c[BR];
	};
private:
	inline ParentChildIds getParentChildId(Node *node) {
		ParentChildIds pci;
		pci.p = node->id;
		for(int i : views::iota(0, BR)) {
			pci.c[i] = node->children[i] ? node->children[i]->id : NO_ID;
		}
		return pci;
	}
public:


	inline LazySegTreeIntervals(int N) : root({createNewNode(), {0, N}}) {
		//DELETEMEassert(N >= 1);
	}


	constexpr static int NO_ID = -1;

	// Ensure that all nodes on the path from the root [0,N) to the
	// leaf [x, x+1) exist. For each such node, returns a tuple
	// with the id of that node and all its children (or NO_ID if a child
	// doesn't exist). These are retured in order from root to leaf.
	vector<ParentChildIds> ensureNodesAndGetIds(int x) {
		//DELETEMEassert(root.ivl.contains(x));

		vector<ParentChildIds> ids;

		NodePtrIvl cur = root;
		while(true) {
			//DELETEMEassert(cur.node);
			//DELETEMEassert(cur.ivl.contains(x));
			if(cur.ivl.length() == 1) {
				ids.push_back(getParentChildId(cur.node));
				break;
			}

			int childIndex = cur.ivl.getChildIndex(x);
			if(!cur.node->children[childIndex]) {
				cur.node->children[childIndex] = createNewNode();
			}
			ids.push_back(getParentChildId(cur.node));
			cur = cur.children()[childIndex]; // can optimize, no need to compute all children
		}
		return ids;
	}

	// 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 vector
	// is at most logarithmic in N.
	vector<int> decomposeIntervalAndGetIds(const Interval &ivl) const {
		vector<int> ids;
		decompose(root, ivl, ids);
		return ids;
	}
};

LazySegTreeIntervals Rtree(1), Ctree(1);


// A key (x,y) corresponds to node with id x in Rtree and
// a node with id y in Ctree. Each of those nodes represent an
// interval of indices. Their product represents a subrectangle
// of cells. The value is the gcd of the values in those cells.
map<pair<int, int>, long long> gcds;

void init(int R, int C) {
	Rtree = LazySegTreeIntervals(R);
	Ctree = LazySegTreeIntervals(C);
}

void update(int P, int Q, long long K) {
	// Each of these is ordered from root to leaf.
	vector<LazySegTreeIntervals::ParentChildIds> rIds = Rtree.ensureNodesAndGetIds(P);
	vector<LazySegTreeIntervals::ParentChildIds> cIds = Ctree.ensureNodesAndGetIds(Q);

	//DELETEMEassert(!rIds.empty());
	//DELETEMEassert(!cIds.empty());

	for (auto rit = rIds.rbegin(); rit != rIds.rend(); ++rit)
	for (auto cit = cIds.rbegin(); cit != cIds.rend(); ++cit) {
		if (rit == rIds.rbegin() && cit == cIds.rbegin()) { // base case
			gcds[{rIds.rbegin()->p, cIds.rbegin()->p}] = K;
			continue;
		}
		// We have a rectangle which can be split in BR rectangles horizontally or vertically.
		// We can choose either arbitrarily, except for a 1xN or Nx1
		// rectangle, in which case there is only one choice.
		long long &z = gcds[{rit->p, cit->p}];
		z=0;
		if (rit == rIds.rbegin()) {
			// q can be NO_ID 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.
			for(int q : cit->c) {
				z = gcd2(z, getOrDefault(gcds, {rit->p, q}, 0LL));
			}
		} else {
			for(int q : rit->c) {
				z = gcd2(z, getOrDefault(gcds, {q, cit->p}, 0LL));
			}
		}
	}
}

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

	long long ans = 0;
	for(int rId : rIds)
	for(int cId : cIds) {
		ans = gcd2(ans, getOrDefault(gcds, {rId, cId}, 0LL));
		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: 0 / 17
• Subtask 5: 0 / 20