NamPE286’s gists

NamPE286 / monotoneChain.cpp

Created September 26, 2023 01:33

Convex Hull (monotone chain algorithm)

	// https://cses.fi/problemset/task/2195/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	ll crossProd(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
	return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
	}

NamPE286 / binaryLifing.cpp

Last active September 16, 2023 04:34

Binary lifting template

	// https://cses.fi/problemset/task/1688/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	class BinaryLifting {
	ll MAXLOG;
	vector<vector<ll>> parent;

NamPE286 / LCABinaryJumping.cpp

Created September 15, 2023 19:15

Lowest common ancestor with binary jumping (binary lifting)

	// https://cses.fi/problemset/task/1688/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	const ll MAXLOG = 18;

	void preCalc(vector<vector<ll>>& parent) {

NamPE286 / binaryJumping.cpp

Last active September 15, 2023 18:57

Binary Jumping (binary lifting)

	// https://cses.fi/problemset/task/1687/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	ll jump(vector<vector<ll>>& parent, ll x, ll k) {
	for(ll i = 0; i <= 18; i++) {
	if(k & (1 << i)) {

NamPE286 / indexed_set.cpp

Created August 9, 2023 13:32

Indexed set template

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	#include <ext/pb_ds/assoc_container.hpp>

	using namespace __gnu_pbds;
	template <class T>
	using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

NamPE286 / kruskal.cpp

Last active August 5, 2023 02:46

Minimum spanning tree (Kruskal)

	// https://cses.fi/problemset/task/1675/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	class DSU {
	private:
	vector<ll> v;

NamPE286 / rollinghash.cpp

Created July 28, 2023 02:34

Rolling hash implementation in C++ (used in Rabin Karp algorithm)

	// https://cses.fi/problemset/task/1753/

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	const ll MOD = 1e9 + 7;

	class rolling_hash {

NamPE286 / trie.cpp

Created July 26, 2023 20:37

Trie implementation in C++

NamPE286 / sqrtDecomp.cpp

Created July 24, 2023 09:27

Square root decomposition

	// https://cses.fi/problemset/task/1648

	#include <bits/stdc++.h>

	using namespace std;
	typedef long long ll;

	class SQRT {
	private:
	vector<ll> blocks, arr;

NamPE286 / pointerSegTreeLazy.cpp

Last active October 31, 2024 00:34

Segment tree with lazy propagation implementation with pointer in C++

Bùi Hùng Nam NamPE286