-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathtemplate.hpp
158 lines (156 loc) · 5.07 KB
/
template.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#pragma once
#include "types.hpp"
using namespace std::ranges;
using namespace std::literals;
// NOLINTBEGIN
#define CONC(a, b) CONC_(a, b)
#define CONC_(a, b) a##b
#define GET0(a, ...) a
#define GET1(a, b, ...) b
#define GET2(a, b, c, ...) c
#define GET3(a, b, c, d, ...) d
#define GET4(a, b, c, d, e, ...) e
#define GET5(a, b, c, d, e, f, ...) f
#define GET_LAST(...) CONC(GET, NARGS(__VA_ARGS__))(, __VA_ARGS__, , , , , , )
#define DROP_LAST1(a)
#define DROP_LAST2(a, b) a
#define DROP_LAST3(a, b, c) a, b
#define DROP_LAST4(a, b, c, d) a, b, c
#define DROP_LAST5(a, b, c, d, e) a, b, c, d
#define DROP_LAST(...) CONC(DROP_LAST, NARGS(__VA_ARGS__))(__VA_ARGS__)
#define NARGS(...) GET5(__VA_ARGS__, 5, 4, 3, 2, 1, 0)
#define FOR1(a) for (std::decay_t<decltype(a)> _ = 0; _ < (a); _++)
#define FOR2(i, a) for (std::decay_t<decltype(a)> i = 0; i < (a); i++)
#define FOR3(i, a, b) for (auto i = (a); i < (b); i++)
#define FOR4(i, a, b, c) for (auto i = (a); i < (b); i += (c))
#define FOR2_R(i, a) for (auto i = (a); i--;)
#define FOR3_R(i, a, b) for (auto i = (b); i-- > (a);)
#define _for(...) GET4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define _for_r(...) GET3(__VA_ARGS__, FOR3_R, FOR2_R)(__VA_ARGS__)
#define M_ID(...) __VA_ARGS__
#define M_BRACKET(...) [__VA_ARGS__]
#define FOREACH_HELPER(...) GET4(__VA_ARGS__, M_BRACKET, M_BRACKET, M_BRACKET, M_ID)(__VA_ARGS__)
#define foreach(...) for (auto&& FOREACH_HELPER(DROP_LAST(__VA_ARGS__)): GET_LAST(__VA_ARGS__))
#define loop while (true)
[[maybe_unused]] struct {
constexpr auto operator->*(auto&& f) const { return f(); }
} blk;
#define BLK blk->*[&]
#define lowbit(x) ((x) & (-(x)))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define LB(c, ...) distance(begin(c), lower_bound(c, __VA_ARGS__))
#define UB(c, ...) distance(begin(c), upper_bound(c, __VA_ARGS__))
#define UNIQUE(c) sort(c), (c).erase(std::unique(all(c)), end(c))
#define VEC(type, a, ...) auto a = vec<type>(__VA_ARGS__)
#define VECI(a, ...) auto a = veci(__VA_ARGS__)
#define FORWARD(x) std::forward<decltype(x)>(x)
#define eb emplace_back
#if defined(LX_LOCAL) || defined(ASSERTIONS)
#define ASSERT(...) assert(__VA_ARGS__)
#else
#define ASSERT(...) void()
#endif
// NOLINTEND
constexpr auto floor(auto&& x, auto&& y) { return x / y - (x % y && (x ^ y) < 0); }
constexpr auto ceil(auto&& x, auto&& y) { return floor(x + y - 1, y); }
constexpr auto divmod(auto x, auto y) {
auto&& q = floor(x, y);
return std::pair{q, x - q * y};
}
template <typename T = u64>
constexpr T ten(int t) { return t == 0 ? 1 : ten<T>(t - 1) * 10; }
constexpr int get_lg(auto n) { return n <= 1 ? 1 : std::__bit_width(n - 1); }
constexpr auto Max(const auto& x) { return x; }
constexpr auto Min(const auto& x) { return x; }
constexpr auto Max(const auto& x, const auto& y, const auto&... arg) { return x < y ? Max(y, arg...) : Max(x, arg...); }
constexpr auto Min(const auto& x, const auto& y, const auto&... arg) { return x < y ? Min(x, arg...) : Min(y, arg...); }
constexpr bool chkmax(auto& d, const auto&... x) {
auto t = Max(x...);
return d < t && (d = t, true);
}
constexpr bool chkmin(auto& d, const auto&... x) {
auto t = Min(x...);
return d > t && (d = t, true);
}
constexpr auto sum(input_range auto&& r) { return std::accumulate(all(r), range_value_t<decltype(r)>{}); }
constexpr auto sum(input_range auto&& r, auto init) { return std::accumulate(all(r), init); }
constexpr int len(auto&& x) { return size(x); }
template <typename T>
auto cumsum(const vc<T>& a) {
int n = len(a);
vc<T> b(n + 1);
_for (i, n)
b[i + 1] = b[i] + a[i];
return b;
}
template <typename T>
auto cumsum(auto&& a) {
int n = len(a);
vc<T> b(n + 1);
_for (i, n)
b[i + 1] = b[i] + a[i];
return b;
}
template <typename T>
auto vec(usize n, auto&&... s) {
if constexpr (!sizeof...(s))
return vc<T>(n);
else
return vc(n, vec<T>(s...));
}
auto veci(usize n, auto&&... s) {
if constexpr (sizeof...(s) == 1)
return vc(n, s...);
else
return vc(n, veci(s...));
}
template <typename T>
vi argsort(const vc<T>& a) {
vi I(len(a));
iota(all(I), 0);
sort(I, [&](int i, int j) { return std::pair{a[i], i} < std::pair{a[j], j}; });
return I;
}
template <typename T>
vc<T> rearrange(const vc<T>& a, const vi& I) {
vc<T> b(len(a));
_for (i, len(a))
b[i] = a[I[i]];
return b;
}
template <input_range R>
vi shift(R&& s, range_value_t<R> c) {
vi a(len(s));
_for (i, len(s))
a[i] = s[i] - c;
return a;
}
auto concat(auto&& a, auto&&... b) {
(a.insert(a.end(), all(b)), ...);
return a;
}
template <typename T>
T pop(vc<T>& q) {
T r = std::move(q.back());
q.pop_back();
return r;
}
template <typename T>
T pop(std::deque<T>& q) {
T r = std::move(q.front());
q.pop_front();
return r;
}
template <typename T, typename S, typename C>
T pop(std::priority_queue<T, S, C>& q) {
T r = q.top();
q.pop();
return r;
}
template <typename T>
constexpr T inf = std::numeric_limits<T>::max() * 0.49;
template <>
constexpr f64 inf<f64> = inf<i64>;
template <>
constexpr ld inf<ld> = inf<i64>;