| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1106894 | RomanLeshchuk | Game (IOI13_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <limits>
template <typename T>
class SparseSegTree
{
public:
SparseSegTree(std::uint64_t size) :
m_baseSize{ (std::uint64_t)1 << (std::uint64_t)std::ceil(std::log2(size)) }
{
}
SparseSegTree(const SparseSegTree& tree) = delete;
SparseSegTree& operator=(const SparseSegTree& tree) = delete;
T query(std::uint64_t l, std::uint64_t r) const
{
return m_root ? m_root->query(0, m_baseSize - 1, l, r) : T{};
}
void update(std::uint64_t pos, const T& val)
{
if (!m_root)
{
m_root = new Node{};
}
m_root->update(0, m_baseSize - 1, pos, val);
}
~SparseSegTree()
{
if (m_root)
{
delete m_root;
}
}
template <typename U>
friend class SparseSegTree2d;
private:
class Node
{
public:
Node() = default;
T query(std::uint64_t lRange, std::uint64_t rRange, std::uint64_t l, std::uint64_t r) const
{
if (l <= lRange && rRange <= r)
{
return m_data;
}
if (rRange < l || r < lRange)
{
return T{};
}
std::uint64_t mid = (lRange + rRange) >> 1;
return T::calc(
m_lChild ? m_lChild->query(lRange, mid, l, r) : T{},
m_rChild ? m_rChild->query(mid + 1, rRange, l, r) : T{}
);
}
void update(std::uint64_t lRange, std::uint64_t rRange, std::uint64_t pos, const T& val)
{
if (lRange == rRange)
{
m_data = val;
return;
}
std::uint64_t mid = (lRange + rRange) >> 1;
if (pos <= mid)
{
if (!m_lChild)
{
m_lChild = new Node{};
}
m_lChild->update(lRange, mid, pos, val);
}
else
{
if (!m_rChild)
{
m_rChild = new Node{};
}
m_rChild->update(mid + 1, rRange, pos, val);
}
m_data = T::calc(
m_lChild ? m_lChild->m_data : T{},
m_rChild ? m_rChild->m_data : T{}
);
}
~Node()
{
if (m_lChild)
{
delete m_lChild;
}
if (m_rChild)
{
delete m_rChild;
}
}
private:
Node* m_lChild = nullptr;
Node* m_rChild = nullptr;
T m_data{};
};
std::uint64_t m_baseSize;
Node* m_root = nullptr;
};
template <typename T>
class SparseSegTree2d
{
public:
SparseSegTree2d(std::uint64_t sizeI, std::uint64_t sizeJ) :
m_baseSizeI{ (std::uint64_t)1 << (std::uint64_t)std::ceil(std::log2(sizeI)) },
m_baseSizeJ{ (std::uint64_t)1 << (std::uint64_t)std::ceil(std::log2(sizeJ)) }
{
}
SparseSegTree2d(const SparseSegTree2d& tree) = delete;
SparseSegTree2d& operator=(const SparseSegTree2d& tree) = delete;
T query(std::uint64_t lI, std::uint64_t rI, std::uint64_t lJ, std::uint64_t rJ) const
{
return m_root ? m_root->query(0, m_baseSizeI - 1, lI, rI, lJ, rJ) : T{};
}
void update(std::uint64_t posI, std::uint64_t posJ, const T& val)
{
if (!m_root)
{
m_root = new Node2d(m_baseSizeJ);
}
m_root->update(0, m_baseSizeI - 1, posI, posJ, val);
}
~SparseSegTree2d()
{
if (m_root)
{
delete m_root;
}
}
private:
class Node2d
{
public:
Node2d(std::uint64_t baseSizeJ) :
m_data(baseSizeJ)
{
}
T query(std::uint64_t lRange, std::uint64_t rRange, std::uint64_t lI, std::uint64_t rI, std::uint64_t lJ, std::uint64_t rJ) const
{
if (lI <= lRange && rRange <= rI)
{
return m_data.query(lJ, rJ);
}
if (rRange < lI || rI < lRange)
{
return T{};
}
std::uint64_t mid = (lRange + rRange) >> 1;
return T::calc(
m_lChild ? m_lChild->query(lRange, mid, lI, rI, lJ, rJ) : T{},
m_rChild ? m_rChild->query(mid + 1, rRange, lI, rI, lJ, rJ) : T{}
);
}
void update(std::uint64_t lRange, std::uint64_t rRange, std::uint64_t posI, std::uint64_t posJ, const T& val)
{
if (lRange == rRange)
{
m_data.update(posJ, val);
return;
}
std::uint64_t mid = (lRange + rRange) >> 1;
if (posI <= mid)
{
if (!m_lChild)
{
m_lChild = new Node2d(m_data.m_baseSize);
}
m_lChild->update(lRange, mid, posI, posJ, val);
}
else
{
if (!m_rChild)
{
m_rChild = new Node2d(m_data.m_baseSize);
}
m_rChild->update(mid + 1, rRange, posI, posJ, val);
}
m_data.update(posJ, T::calc(
m_lChild ? m_lChild->m_data.query(posJ, posJ) : T{},
m_rChild ? m_rChild->m_data.query(posJ, posJ) : T{}
));
}
~Node2d()
{
if (m_lChild)
{
delete m_lChild;
}
if (m_rChild)
{
delete m_rChild;
}
}
private:
Node2d* m_lChild = nullptr;
Node2d* m_rChild = nullptr;
SparseSegTree<T> m_data;
};
std::uint64_t m_baseSizeI;
std::uint64_t m_baseSizeJ;
Node2d* m_root = nullptr;
};
struct Gcd
{
std::uint64_t val = 0;
static Gcd calc(const Gcd& left, const Gcd& right)
{
std::uint64_t a = left.val, b = right.val;
if (!a)
{
return Gcd{ b };
}
if (!b)
{
return Gcd{ a };
}
if (b > a)
{
std::swap(a, b);
}
while (b)
{
a %= b;
std::swap(a, b);
}
return Gcd{ a };
}
};
SparseSegTree2d<Gcd>* tree = nullptr;
void init(int R, int C) {
tree = new SparseSegTree2d<Gcd>(R, C);
}
void update(int P, int Q, long long K) {
tree->update(P, Q, Gcd{ (std::uint64_t)K });
}
long long calculate(int P, int Q, int U, int V) {
return tree->query(P, U, Q, V).val;
}
using namespace std;
int main()
{
init(2, 3);
update(0, 0, 20);
update(0, 2, 15);
update(1, 1, 12);
cout << calculate(0, 0, 0, 2) << '\n';
cout << calculate(0, 0, 1, 1) << '\n';
return 0;
}