CompetitiveProgrammingCpp
This documentation is automatically generated by online-judge-tools/verification-helper
Test/DataStructure/Accumulation2D_sum.test.cpp
- View this file on GitHub
- Last update: 2024-12-27 16:29:20+09:00
- Problem: https://yukicoder.me/problems/no/1623
Depends on
- Library/Algebraic/Group.hpp
- Library/DataStructure/Accumulation.hpp
- Library/DataStructure/Accumulation2D.hpp
Code
#define PROBLEM "https://yukicoder.me/problems/no/1623"
#include <iostream>
// begin:tag includes
#include "./../../Library/DataStructure/Accumulation2D.hpp"
// end:tag includes
using ll = long long;
signed main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int n;
std::cin >> n;
constexpr ll size = 3e3 + 1;
std::vector<ll> rv;
rv.reserve(n);
for (int _ = 0; _ < n; ++_) {
int r;
std::cin >> r;
rv.emplace_back(r);
}
std::vector<ll> gc(size), bc(size);
for (int _ = 0; _ < n; ++_) {
int b;
std::cin >> b;
++bc[b];
}
for (int _ = 0; _ < n; ++_) {
int g;
std::cin >> g;
++gc[g];
}
std::vector<std::vector<ll>> table(size, std::vector<ll>(2 * size));
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j) {
table[std::max(i, j)][i + j] += gc[i] * bc[j];
}
auto acc = mtd::Accumulation2D<>(table);
ll ans = 0;
for (const auto& r : rv) { ans += acc.get(0, r + 1, r, 2 * size - 1); }
std::cout << ans << std::endl;
}#line 1 "Test/DataStructure/Accumulation2D_sum.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1623"
#include <iostream>
// begin:tag includes
#line 2 "Library/DataStructure/Accumulation2D.hpp"
#include <vector>
#line 2 "Library/Algebraic/Group.hpp"
#line 4 "Library/Algebraic/Group.hpp"
namespace mtd {
template <class S, // set
S element, // identity element
class op, // binary operation
class inv // inverse operation
>
requires std::is_invocable_r_v<S, op, S, S>
struct Group {
using value_type = S;
constexpr static S _element = element;
using op_type = op;
using inv_type = inv;
S m_val;
constexpr Group() : m_val(element) {}
constexpr Group(S val) : m_val(val) {}
constexpr Group inverse() const { return inv()(m_val); }
constexpr Group binaryOperation(const Group& g) const {
return op()(m_val, g.m_val);
}
constexpr friend std::ostream& operator<<(
std::ostream& os, const Group<S, element, op, inv>& g) {
return os << g.m_val;
}
};
namespace __detail {
template <typename T,
template <typename, auto, typename, typename> typename S>
concept is_group_specialization_of = requires {
typename std::enable_if_t<
std::is_same_v<T, S<typename T::value_type, T::_element,
typename T::op_type, typename T::inv_type>>>;
};
} // namespace __detail
template <typename G>
concept group = __detail::is_group_specialization_of<G, Group>;
} // namespace mtd
#line 2 "Library/DataStructure/Accumulation.hpp"
#include <algorithm>
#line 5 "Library/DataStructure/Accumulation.hpp"
#line 7 "Library/DataStructure/Accumulation.hpp"
namespace mtd {
namespace type {
using inv = decltype([](auto x) { return -x; });
using op = decltype([](auto x, auto y) { return x + y; });
template <class P>
using AdditiveGroup = Group<P, P(0), op, inv>;
} // namespace type
template <group Group = type::AdditiveGroup<long long>>
class Accumulation {
using S = decltype(Group().m_val);
const int size;
std::vector<Group> sumList;
public:
constexpr Accumulation() = delete;
constexpr Accumulation(const std::vector<Group>& v)
: size(v.size()), sumList(size + 1) {
for (int i = 0; i < size; ++i) {
sumList[i + 1] = sumList[i].binaryOperation(v[i]);
}
}
constexpr Accumulation(const std::vector<S>& v)
: Accumulation(std::vector<Group>(v.begin(), v.end())) {}
constexpr auto get(int n) const { return sumList[n + 1].m_val; }
constexpr auto get(int l, int r) const {
if (r < l) { return Group::_element; }
l = std::max(l, 0);
r = std::min(r, size - 1);
return sumList[r + 1].binaryOperation(sumList[l].inverse()).m_val;
}
constexpr friend std::ostream& operator<<(std::ostream& os,
const Accumulation<Group>& acc) {
for (const auto& x : acc.sumList) { os << x << " "; }
return os;
}
};
} // namespace mtd
#line 6 "Library/DataStructure/Accumulation2D.hpp"
namespace mtd {
template <group Group = type::AdditiveGroup<long long>>
class Accumulation2D {
private:
using S = decltype(Group().m_val);
const int h;
const int w;
std::vector<std::vector<Group>> sumList;
public:
constexpr Accumulation2D() = delete;
constexpr Accumulation2D(const std::vector<std::vector<S>>& v)
: h(v.size()),
w(v[0].size()),
sumList(h + 1, std::vector<Group>(w + 1)) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) { sumList[i + 1][j + 1] = v[i][j]; }
}
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w + 1; ++j) {
sumList[i + 1][j] = sumList[i + 1][j].binaryOperation(sumList[i][j]);
}
}
for (int i = 0; i < h + 1; ++i) {
for (int j = 0; j < w; ++j) {
sumList[i][j + 1] = sumList[i][j + 1].binaryOperation(sumList[i][j]);
}
}
}
constexpr S get(int y, int x) { return sumList[y + 1][x + 1].m_val; }
constexpr S get(int y1, int x1, int y2, int x2) {
if (y2 < y1 || x2 < x1) { return Group().m_val; }
x1 = std::max(x1, 0);
y1 = std::max(y1, 0);
y2 = std::min(y2, h - 1);
x2 = std::min(x2, w - 1);
return sumList[y2 + 1][x2 + 1]
.binaryOperation(sumList[y1][x1])
.binaryOperation(sumList[y2 + 1][x1].inverse())
.binaryOperation(sumList[y1][x2 + 1].inverse())
.m_val;
}
};
} // namespace mtd
#line 7 "Test/DataStructure/Accumulation2D_sum.test.cpp"
// end:tag includes
using ll = long long;
signed main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int n;
std::cin >> n;
constexpr ll size = 3e3 + 1;
std::vector<ll> rv;
rv.reserve(n);
for (int _ = 0; _ < n; ++_) {
int r;
std::cin >> r;
rv.emplace_back(r);
}
std::vector<ll> gc(size), bc(size);
for (int _ = 0; _ < n; ++_) {
int b;
std::cin >> b;
++bc[b];
}
for (int _ = 0; _ < n; ++_) {
int g;
std::cin >> g;
++gc[g];
}
std::vector<std::vector<ll>> table(size, std::vector<ll>(2 * size));
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j) {
table[std::max(i, j)][i + j] += gc[i] * bc[j];
}
auto acc = mtd::Accumulation2D<>(table);
ll ans = 0;
for (const auto& r : rv) { ans += acc.get(0, r + 1, r, 2 * size - 1); }
std::cout << ans << std::endl;
}