Submission #1113071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113071		Noam527	Game (IOI13_game)	C++17	100 / 100	2130 ms	150768 KiB

game

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = (int)1e9 + 7;
const ll inf = 2e18;
const int OO = 1;
using namespace std;
 
#include "game.h"
 
template<int D, typename element, ll N>
struct segtree {
	template<int d> using sdim = segtree<d, element, N>;
#define mid (nl + (nr - nl) / 2) // IMP: undef in the end
#define templatic template<class... T>
	struct node {
		int c[2];
		sdim<D - 1> val;
		node() { c[0] = c[1] = 0; }
		int& operator[](int i) { return c[i]; };
	};
	vector<node> t;
	static constexpr int LIM = (D == 1) * 64; // 64 or 128
	vector<pair<ll, element>> cache;

	segtree() : t(1) {}
	int add_node() {
		t.push_back(node());
		return (int)t.size() - 1;
	}
	int go(int n, int d) {
		if (!t[n][d]) {
			int x = add_node();
			t[n][d] = x;
		}
		return t[n][d];
	}
	templatic element get(ll i, T... nxt) {
		if (t.size() == 1) {
			element res;
			for (auto& x : cache)
				if (x.first == i) res = x.second;
			return res;
		}
		int n = 0; ll l = 0, r = N, m;
		do {
			m = l + (r - l) / 2;
			if (i < m) n = t[n][0], r = m;
			else n = t[n][1], l = m;
		} while (n && l + 1 < r);
		if (!n) return element();
		return t[n].val.get(nxt...);
	}
	templatic element update(element x, ll i, T... nxt) {
		if (t.size() == 1) {
			bool found = false;
			for (auto& v : cache)
				if (v.first == i) v.second = x, found = true;
			if (!found) cache.emplace_back(i, x);
			if (cache.size() < LIM) return x;
			for (auto& v : cache)
				upd(v.second, 0, 0, N, v.first, nxt...);
			return cache.clear(), x;
		}
		return upd(x, 0, 0, N, i, nxt...);
	}
	templatic element upd(element x, ll n, ll nl, ll nr, ll i, T... nxt) {
		if (nl + 1 == nr) return t[n].val.update(x, nxt...) , x;
		int d = i >= mid;
		(i < mid ? nr : nl) = mid;
		element lx = upd(x, go(n, d), nl, nr, i, nxt...), rx;
		if (t[n][!d]) rx = t[t[n][!d]].val.get(nxt...);
		return t[n].val.update(lx * rx, nxt...) , lx * rx;
	}
	templatic element query(ll l, ll r, T... nxt) {
		if (t.size() == 1) {
			element res;
			for (auto& x : cache)
				if (l <= x.first && x.first < r)
					res = res * x.second;
			return res;
		}
		return que(0, 0, N, l, r, nxt...);
	}
	templatic element que(ll n, ll nl, ll nr, ll l, ll r, T... nxt) {
		if (nr <= l || r <= nl) return element();
		if (l <= nl && nr <= r) return t[n].val.query(nxt...);
		return (t[n][0] ? que(t[n][0], nl, mid, l, r, nxt...) : element()) *
			(t[n][1] ? que(t[n][1], mid, nr, l, r, nxt...) : element());
	}
};
template<typename element, ll N>
struct segtree<0, element, N> {
	element val;
	segtree() {}
	element get() { return val; }
	element query() { return val; }
	element update(element x) {
		return val = x;
	}
};
 
ll gcd(ll x, ll y) {
	return !y ? x : gcd(y, x % y);
}
 
struct ele {
	ll x;
	ele(ll xx = 0) : x(xx) {}
	ele operator * (const ele &a) const {
		return ele(gcd(x, a.x));
	}
};
 
segtree<2, ele, 1000000005> T;
 
void init(int R, int C) {
	// nothing...
}
 
void update(int p, int q, ll k) {
	T.update(ele(k), p, q);
}
 
ll calculate(int p, int q, int u, int v) {
	return T.query(p, u + 1, q, v + 1).x;
}

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