raybbian's CP Algos
This documentation is automatically generated by competitive-verifier/competitive-verifier
main.cpp
- View this file on GitHub
- Last update: 2024-12-11 17:30:10-05:00
Depends on
algo/common.h- algo/debug/debug.h
- algo/debug/preamble.h
- algo/ds/common.h
- algo/ds/dsu.h
- algo/ds/fenwick.h
- algo/ds/sparse_table.h
- algo/math/common.h
- algo/math/modint.h
- algo/utils/bits.h
Code
#include "algo/common.h"
#include "algo/debug/preamble.h"
/* start include */
#include "algo/ds/dsu.h"
#include "algo/ds/fenwick.h"
#include "algo/ds/sparse_table.h"
#include "algo/math/modint.h"
/* end include */
#include "algo/debug/debug.h"
using namespace std;
using namespace algo;
void solve() {
vector<bool> a = {1, 0, 0, 1, 1, 1, 0, 1};
math::mint::set_mod(1000000007);
math::mint b = 321931720389;
vector<math::mint> c = {102380918203, 321378012937, 31231231208,
3213010101};
string d = "TNASRIEOTNRIAS";
ds::dsu dsu(10);
dsu.unite(0, 1);
dsu.unite(0, 2);
dsu.unite(0, 3);
dsu.unite(0, 4);
dsu.unite(5, 6);
bitset<10> bs(2138);
ds::fenwick<math::mint> t({5, 1, 3, 2, 6});
t.add(2, 10);
ds::sparse_table<int> st({5, 1, 2, 3, 4, 6},
[&](int a, int b) { return std::min(a, b); });
tuple lots{t, st, dsu, a, c};
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
array<int, 5> arr{0, 1, 2, 3, -1};
priority_queue<int> pq(arr.begin(), arr.end());
queue<int> q(arr.begin(), arr.end());
std::complex<float> cpx{1.0, 2.0};
dbg(a, b, c, "hi", d, dsu, t, st, st.query(1, 3), bs, lots, dirs, arr, q,
pq, cpx);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
}
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#endif
namespace algo {}
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 3 "algo/debug/preamble.h"
template <typename T>
concept printable = requires(T t) {
{ std::cout << t } -> std::same_as<std::ostream &>;
};
template <typename T>
concept iterable = std::ranges::range<T> && (!printable<T>);
template <typename... T>
inline void no_debug(T... _) {
}
template <size_t N>
std::ostream &operator<<(std::ostream &os, const std::bitset<N> &v);
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, std::queue<T, U> q);
template <typename T, typename U, typename V>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T, U, V> pq);
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p);
template <typename... T>
std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t);
template <iterable T>
std::ostream &operator<<(std::ostream &os, const T &t);
#line 3 "main.cpp"
/* start include */
#line 3 "algo/ds/dsu.h"
namespace algo::ds {
template <bool union_by_size = true, bool path_compression = true>
struct dsu {
dsu(int n) : e(std::vector<int>(n, -1)) {
}
int get(int x) {
if (e[x] < 0) return x;
if (path_compression) return e[x] = get(e[x]);
return get(e[x]);
}
bool is_same(int a, int b) {
return get(a) == get(b);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (union_by_size && e[x] > e[y]) std::swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
friend std::ostream &operator<<(std::ostream &os, dsu s) {
os << "[";
bool first = true;
for (int i = 0; i < sz(s.e); i++) {
if (s.get(i) == i) {
if (!first) os << ", ";
first = false;
os << "[" << i;
for (int j = 0; j < sz(s.e); j++) {
if (j != i && s.get(j) == i) {
os << ", " << j;
}
}
os << "]";
}
}
return os << "]";
}
private:
std::vector<int> e;
};
} // namespace algo::ds
#line 3 "algo/ds/fenwick.h"
namespace algo::ds {
template <typename T>
struct fenwick {
fenwick(int _n) : n(_n), bit(n, 0) {
}
fenwick(const std::vector<T> &a) : fenwick(sz(a)) {
for (int i = 0; i < n; i++) {
bit[i] += a[i];
int r = i | (i + 1);
if (r < n) bit[r] += bit[i];
}
}
// Inclusive on [l, r]
T sum(int l, int r) {
return sum(r) - sum(l - 1);
}
T val(int pos) {
return sum(pos, pos);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
friend std::ostream &operator<<(std::ostream &os, fenwick f) {
os << "[";
bool first = true;
for (int i = 0; i < f.n; i++) {
if (!first) os << ", ";
first = false;
os << f.val(i);
}
os << "]";
return os;
}
private:
int n;
std::vector<T> bit;
T sum(int r) {
T ret(0);
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
};
} // namespace algo::ds
#line 3 "algo/ds/common.h"
namespace algo::ds {
template <typename T>
T min(const T &a, const T &b) {
return std::min(a, b);
}
}; // namespace algo::ds
#line 3 "algo/utils/bits.h"
namespace algo::utils {
// Returns number of set bits in x
constexpr int popcnt(int64_t x) {
return __builtin_popcountll(x);
}
// Returns floor(log_2(x))
constexpr int lg2(uint64_t x) {
return std::bit_width(x) - 1;
}
} // namespace algo::utils
#line 5 "algo/ds/sparse_table.h"
namespace algo::ds {
template <typename T>
struct sparse_table {
// Must be constructed with idempotent function. Call init() after if using
// this constructor.
sparse_table(int _n, const std::function<T(T, T)> &op = min<T>)
: n(_n), k(utils::lg2(n)), op(op), st(k + 1, std::vector<T>(n)) {
}
// Must be constructed with idempotent function
sparse_table(const std::vector<T> &a,
const std::function<T(T, T)> &op = min<T>)
: sparse_table(sz(a), op) {
init(a);
}
void init(const std::vector<T> &a) {
assert(sz(a) <= n);
std::copy(all(a), st[0].begin());
for (int i = 1; i <= k; i++) {
for (int j = 0; j + (1 << i) <= n; j++) {
st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
// Queries on [l, r]
T query(int l, int r) {
int i = utils::lg2(r - l + 1);
return op(st[i][l], st[i][r - (1 << i) + 1]);
}
friend std::ostream &operator<<(std::ostream &os, const sparse_table &t) {
return os << t.st[0];
}
private:
int n, k;
std::function<T(T, T)> op;
std::vector<std::vector<T>> st;
};
} // namespace algo::ds
#line 3 "algo/math/common.h"
#ifdef ALGO_MAXN
const int MAXN = ALGO_MAXN;
#else
const int MAXN = 1 << 19;
#endif
namespace algo::math {
constexpr int64_t safe_mod(int64_t x, int64_t m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Returns (x ** n) % m
constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) {
assert(0 <= n);
assert(1 <= m);
if (m == 1) return 0;
uint _m = (uint)(m);
uint64_t r = 1;
uint64_t y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
struct barrett {
explicit barrett(uint64_t _m) : m(_m), im(-1ULL / _m) {
assert(1 <= _m);
}
uint64_t mod() {
return m;
};
uint64_t reduce(uint64_t a) {
uint64_t q = (uint64_t)((__uint128_t(im) * a) >> 64);
uint64_t r = a - q * m;
return r - (r >= m) * m;
}
private:
uint64_t m, im;
};
constexpr int64_t c_div(int64_t a, int64_t b) {
return a / b + ((a ^ b) > 0 && a % b);
}
constexpr int64_t f_div(int64_t a, int64_t b) {
return a / b - ((a ^ b) < 0 && a % b);
}
auto bpow(auto const &x, auto n, auto const &one, auto op) {
if (n == 0) {
return one;
} else {
auto t = bpow(x, n / 2, one, op);
t = op(t, t);
if (n % 2) {
t = op(t, x);
}
return t;
}
}
auto bpow(auto x, auto n, auto ans) {
return bpow(x, n, ans, std::multiplies{});
}
template <typename T>
T bpow(T const &x, auto n) {
return bpow(x, n, T(1));
}
// Returns a pair(g, x) s.t. g = gcd(a, n), xa = g (mod n), 0 <= x < n/g
// If r > 1 then a is not invertible mod n
constexpr std::pair<int64_t, int64_t> inv_gcd(int64_t a, int64_t n) {
a = safe_mod(a, n);
if (a == 0) return {n, 0};
int64_t t = 0, newt = 1;
int64_t r = n, newr = a;
while (newr) {
int64_t quotient = r / newr;
r -= newr * quotient;
t -= newt * quotient;
std::swap(r, newr);
std::swap(t, newt);
}
if (t < 0) t += n / r;
return {r, t};
}
} // namespace algo::math
#line 4 "algo/math/modint.h"
namespace algo::math {
template <int id>
struct modint {
static int mod() {
return bt.mod();
}
static void set_mod(int m) {
assert(1 <= m);
bt = barrett(m);
}
auto static with_mod(int tmp, auto callback) {
struct scoped {
int prev = mod();
~scoped() {
set_mod(prev);
}
} _;
set_mod(tmp);
return callback();
}
modint() : v(0) {
}
modint(int64_t _v) {
v = (-mod() < _v && _v < mod()) ? _v : _v % mod();
if (v < 0) v += mod();
}
modint &operator+=(const modint &other) {
v += other.v;
if (v >= mod()) v -= mod();
return *this;
}
modint &operator-=(const modint &other) {
v -= other.v;
if (v < 0) v += mod();
return *this;
}
modint &operator*=(const modint &other) {
v = bt.reduce((int64_t)v * other.v);
return *this;
}
modint &operator/=(const modint &other) {
return *this = *this * other.inv();
}
int &operator++() {
v++;
if (v == mod()) v = 0;
return *this;
}
modint &operator--() {
if (v == 0) v = mod();
v--;
return *this;
}
modint operator++(int) {
modint result = *this;
++*this;
return result;
}
modint operator--(int) {
modint result = *this;
--*this;
return result;
}
friend modint operator+(modint a, const modint &b) {
return a += b;
}
friend modint operator-(modint a, const modint &b) {
return a -= b;
}
friend modint operator*(modint a, const modint &b) {
return a *= b;
}
friend modint operator/(modint a, const modint &b) {
return a /= b;
}
friend modint operator-(modint a) {
return 0 - a;
}
modint inv() const {
auto eg = inv_gcd(v, mod());
assert(eg.first == 1);
return eg.second;
}
friend bool operator==(const modint &a, const modint &b) {
return a.v == b.v;
}
friend bool operator!=(const modint &a, const modint &b) {
return !(a == b);
}
explicit operator int() const {
return v;
}
friend std::ostream &operator<<(std::ostream &os, const modint &a) {
return os << a.v;
}
friend std::istream &operator>>(std::istream &is, modint &a) {
is >> a.v;
a.v = (mod() < a.v && a.v < mod()) ? a.v : a.v % mod();
if (a.v < 0) a.v += mod();
return is;
}
private:
int v;
static barrett bt;
};
template <int id>
barrett modint<id>::bt(998244353);
using mint = modint<-1>;
} // namespace algo::math
#line 9 "main.cpp"
/* end include */
#line 4 "algo/debug/debug.h"
template <size_t N>
std::ostream &operator<<(std::ostream &os, const std::bitset<N> &v) {
os << "<";
for (size_t i = 0; i < N; i++) {
os << static_cast<char>('0' + v[i]);
}
return os << ">";
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, std::queue<T, U> q) {
os << "[";
bool first = true;
for (; !q.empty(); q.pop()) {
if (!first) os << ", ";
first = false;
os << q.front();
}
return os << "]";
}
template <typename T, typename U, typename V>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T, U, V> pq) {
os << "[";
bool first = true;
for (; !pq.empty(); pq.pop()) {
if (!first) os << ", ";
first = false;
os << pq.top();
}
return os << "]";
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template <typename... T>
std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t) {
os << "(";
bool first = true;
auto print = [&os, &first](auto arg) {
if (!first) os << ", ";
first = false;
os << arg;
};
std::apply([&print](auto &&...args) { (print(args), ...); }, t);
return os << ")";
}
template <iterable T>
std::ostream &operator<<(std::ostream &os, const T &t) {
os << "[";
bool first = true;
for (const auto &e : t) {
if (!first) os << ", ";
first = false;
os << e;
}
return os << "]";
}
template <typename T>
void debug(std::string name, T var) {
std::cerr << "\x1B[31m" << name << ": " << var << "\x1B[0m" << '\n';
}
// https://www.scs.stanford.edu/~dm/blog/va-opt.html
#define PARENS ()
#define EXPAND(...) EXPAND4(EXPAND4(EXPAND4(EXPAND4(__VA_ARGS__))))
#define EXPAND4(...) EXPAND3(EXPAND3(EXPAND3(EXPAND3(__VA_ARGS__))))
#define EXPAND3(...) EXPAND2(EXPAND2(EXPAND2(EXPAND2(__VA_ARGS__))))
#define EXPAND2(...) EXPAND1(EXPAND1(EXPAND1(EXPAND1(__VA_ARGS__))))
#define EXPAND1(...) __VA_ARGS__
#define FOR_EACH(macro, ...) \
__VA_OPT__(EXPAND(FOR_EACH_HELPER(macro, __VA_ARGS__)))
#define FOR_EACH_HELPER(macro, a1, ...) \
macro(a1) __VA_OPT__(FOR_EACH_AGAIN PARENS(macro, __VA_ARGS__))
#define FOR_EACH_AGAIN() FOR_EACH_HELPER
#define DEBUG(x) debug(#x, x);
#ifdef LOCAL
#define dbg(...) FOR_EACH(DEBUG, __VA_ARGS__) no_debug()
#else
#define dbg(...) no_debug(__VA_ARGS__)
#endif
#line 12 "main.cpp"
using namespace std;
using namespace algo;
void solve() {
vector<bool> a = {1, 0, 0, 1, 1, 1, 0, 1};
math::mint::set_mod(1000000007);
math::mint b = 321931720389;
vector<math::mint> c = {102380918203, 321378012937, 31231231208,
3213010101};
string d = "TNASRIEOTNRIAS";
ds::dsu dsu(10);
dsu.unite(0, 1);
dsu.unite(0, 2);
dsu.unite(0, 3);
dsu.unite(0, 4);
dsu.unite(5, 6);
bitset<10> bs(2138);
ds::fenwick<math::mint> t({5, 1, 3, 2, 6});
t.add(2, 10);
ds::sparse_table<int> st({5, 1, 2, 3, 4, 6},
[&](int a, int b) { return std::min(a, b); });
tuple lots{t, st, dsu, a, c};
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
array<int, 5> arr{0, 1, 2, 3, -1};
priority_queue<int> pq(arr.begin(), arr.end());
queue<int> q(arr.begin(), arr.end());
std::complex<float> cpx{1.0, 2.0};
dbg(a, b, c, "hi", d, dsu, t, st, st.query(1, 3), bs, lots, dirs, arr, q,
pq, cpx);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
}