This file contains 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 <typename T> | |
class LazySegmentTree { | |
vector<T> data_; | |
vector<T> lazy_; | |
int size_; | |
void Eval(int k) { | |
if (lazy_[k] == 0) { | |
return; | |
} |
This file contains 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 ntersects(double ax, double ay, double bx, double by, double cx, | |
double cy, double dx, double dy) { | |
double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax); | |
double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx); | |
double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx); | |
double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx); | |
return tc * td < 0 && ta * tb < 0; | |
}; |
This file contains 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
vector<vector<int>> Dim2PartialSum(vector<vector<int>> &mat, int w, int h) { | |
vector<vector<int>> psum(h + 1, vector<int>(w + 1, 0)); | |
for (int i = 0; i < h; ++i) { | |
for (int j = 0; j < w; ++j) { | |
psum[i + 1][j + 1] = | |
psum[i + 1][j] + psum[i][j + 1] + mat[i][j] - psum[i][j]; | |
} | |
} | |
return psum; |
This file contains 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 Edge { | |
int from, to, cost; | |
Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {} | |
}; | |
vector<optional<int>> BellmanFord(vector<Edge> &edges, int src, int node_size) { | |
vector<optional<int>> dists(node_size); | |
dists[src] = 0; | |
for (int i = 0; i < node_size; ++i) { | |
for (auto &e : edges) { |
This file contains 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
double l = 0, r = 1000; | |
for (int i = 0; i < 80; ++i) { | |
double c1, c2; | |
c1 = (l * 2 + r) / 3; | |
c2 = (l + r * 2) / 3; | |
if (f(c1) > f(c2)) { | |
l = c1; | |
} else { | |
r = c2; | |
} |
This file contains 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 Edge { | |
int to, cap, rev; | |
Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {} | |
}; | |
void AddEdge(vector<vector<Edge>> &g, int from, int to, int cap) { | |
int idx = g[to].size(), rev_idx = g[from].size(); | |
g[from].emplace_back(to, cap, idx); | |
g[to].emplace_back(from, 0, rev_idx); | |
} |
This file contains 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
class Eratosthenes { | |
private: | |
vector<bool> is_prime_; | |
public: | |
Eratosthenes(int max_n): is_prime_(max_n + 1, true) { | |
is_prime_[0] = is_prime_[1] = false; | |
for (int i = 2; i < is_prime_.size(); i++) { | |
if (!is_prime_[i]) { | |
continue; | |
} |
This file contains 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
using ll = long long; | |
ll Inchworm(vector<ll> &va, ll k) { | |
ll left, right, sum, ans; | |
left = right = sum = ans = 0; | |
while (left < va.size()) { | |
while (right < n && sum + va[right] < k) { | |
sum += va[right]; | |
right++; | |
} |
This file contains 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 LcsLen(string &s, string &t, vector<vector<int>> &memo, int i, int j) { | |
if (i < 0 || j < 0) { | |
return 0; | |
} | |
if (memo[i][j] < 0) { | |
if (s[i] == t[j]) { | |
memo[i][j] = LcsLen(s, t, memo, i - 1, j - 1) + 1; | |
} else { | |
memo[i][j] = |
This file contains 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
ll left = 0, right = max_n; | |
while (right - left > 1) { | |
ll mid = (left + right) / 2; | |
if (check(va, vf, mid, k)) { | |
right = mid; | |
} else { | |
left = mid; | |
} | |
} |