This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct timeit { | |
decltype(chrono::high_resolution_clock::now()) begin; | |
const string label; | |
timeit(string label = "???") : label(label) { begin = chrono::high_resolution_clock::now(); } | |
~timeit() { | |
auto end = chrono::high_resolution_clock::now(); | |
auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count(); | |
cerr << duration << "ms elapsed [" << label << "]" << endl; | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct GC { | |
char buf[1 << 16 | 1]; | |
int bc = 0, be = 0; | |
char operator()() { | |
if (bc >= be) { | |
be = fread(buf, 1, sizeof(buf) - 1, stdin); | |
buf[be] = bc = 0; | |
} | |
return buf[bc++]; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int dfs(int cur, int prv = -1, int d = 0) { | |
dist[cur] = d; | |
int mx = cur; | |
for (auto i : adj[cur]) { | |
if (i == prv) | |
continue; | |
int res = dfs(i, cur, d + 1); | |
if (dist[res] > dist[mx]) | |
mx = res; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void rec(int from, int to, function<int(int)> f, int &i, int &p, int q, vector<array<int, 3>> &ints) { | |
if (p == q) | |
return; | |
if (from == to) { | |
ints.push_back({i, to, p}); | |
i = to; | |
p = q; | |
} else { | |
int mid = (from + to) >> 1; | |
rec(from, mid, f, i, p, f(mid), ints); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
map<int, int> comp, decomp; | |
int A[]; | |
// insert everything into map; | |
for (int i=0; i<N; i++) | |
comp[A[i]]=0; | |
int idx=0; | |
for (auto &i: comp) | |
i.second = idx++, decomp[i.second] = i.first; | |
for (int i=0; i<N; i++) | |
A[i] = comp[A[i]]; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int fac; | |
template <class It> int perm_to_int(It begin, It end) { | |
int x = 0, n = 0; | |
for (It i = begin; i != end; ++i, ++n) | |
if (*i < *begin) | |
++x; | |
int val = 0; | |
if (n > 2) | |
val = perm_to_int(++begin, end); | |
else |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
bool isPrime(ull n) { | |
if (n < 2 || n % 2 == 0 || n % 3 == 0) | |
return n - 2 < 2; | |
ull s = __builtin_ctzll(n - 1), d = n >> s; // counts trailing zeros | |
for (auto a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { | |
ull p = binExp(a, d, n), i = s; | |
while (p != 1 && p != n - 1 && a % n && i--) | |
p = binExp(p, 2, n); | |
if (p != n - 1 && i != s) | |
return 0; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
typedef unsigned long long ull; | |
ull sumsq(ull to) { return to / 2 * ((to - 1) | 1); } | |
ull divsum(ull to, ull c, ull k, ull m) { | |
ull res = k / m * sumsq(to) + c / m * to; | |
k %= m, c %= m; | |
if (!k) | |
return res; | |
ull to2 = (to * k + c) / m; | |
return res + (to - 1) * to2 - divsum(to2, m - 1 - c, m, k); | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <int maxn> struct FFT { | |
constexpr static int lg2(int n) { return 32 - __builtin_clz(n - 1); } | |
const static int MAXN = 1 << lg2(maxn); | |
typedef complex<double> cpx; | |
int rev[MAXN]; | |
cpx rt[MAXN]; | |
FFT() { | |
rt[1] = cpx{1, 0}; | |
for (int k = 2; k < MAXN; k *= 2) { | |
cpx z[] = {1, polar(1.0, M_PI / k)}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
pair<bool, array<int, 2>> canMerge(array<int, 4> pts) { | |
auto cmp = [&](int a, int b) { return make_pair(lca.depth[a], a) > make_pair(lca.depth[b], b); }; | |
sort(pts.begin(), pts.end(), cmp); | |
do { | |
if (lca.dist(pts[0], pts[1]) + lca.dist(pts[1], pts[2]) + lca.dist(pts[2], pts[3]) == lca.dist(pts[0], pts[3])) | |
return {true, {pts[0], pts[3]}}; | |
} while (next_permutation(pts.begin() + 1, pts.end(), cmp)); | |
return {false, {0, 0}}; | |
} |