Chillee

struct AhoCorasick {
    struct Vertex {
        int next[MAXCHAR], go[MAXCHAR];
        int leaf = -1;
        int p = -1;
        char pch;
        int link = -1, leaflink = -1;

        Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
            fill(begin(next), end(next), -1);

Chillee

/** Constants Start **/
const double PI = acos(-1.0);
const double EPS = 1e-8;
const double INF = 1e9 + 5;
template <typename T> int sgn(T x) { return x < -EPS ? -1 : x > EPS; }
/** Constants End **/
/** Base Start **/
struct pt {
    T x, y;
    pt operator+(pt p) { return {x + p.x, y + p.y}; }

Chillee

/**
 * Author: 
 * Description: link-cut Tree. Supports BST-like augmentations. (Can be used in place of HLD).
 * Current implementation supports update value at a node, and query max on a path.
 * For details about the structure, refer to https://en.wikipedia.org/wiki/Link/cut_tree
 * Tested on: http://acm.timus.ru/problem.aspx?num=1553
 * Status: Passes existing fuzz tests (with function names modified).
 */
struct Node {
	bool flip = 0;

Chillee

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]];

Chillee

struct H {
    ull x;
    H(ull x = 0) : x(x) {}
    ull get() const { return x; }
    const static ull M = (1ull << 61) - 1;
    H operator+(H o) {
        o.x += x + 1;
        o.x = (o.x & M) + (o.x >> 61);
        return o.x - 1;
    }

Chillee

template <int MAXN> struct Dsu {
    int par[MAXN], sz[MAXN];
    void init(int n) { iota(par, par + n, 0), fill(sz, sz + n, 1); }
    int root(int v) { return v == par[v] ? v : (par[v] = root(par[v])); }

    void merge(int a, int b) {
        if ((a = root(a)) == (b = root(b)))
            return;
        if (sz[a] < sz[b])
            swap(a, b);

Chillee

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

struct node {
    node *l = nullptr, *r = nullptr;
    int val, key = rnd();
    int sz = 1;
    node(int value) : val(value) {}
    ~node() { delete l, delete r; }
    node *upd() {

Chillee

  struct matrix {
    vector<vector<ll>> cells;

    matrix(vector<vector<ll>> input) : cells(input) {}
    matrix(ll n, ll m, ll val) {
        cells.resize(n);
        vector<ll> row(m);
        fill(row.begin(), row.end(), val);
        fill(cells.begin(), cells.end(), row);
    }

Chillee

struct SuffixArray { // sa[0] = n, sa[i] = i-th in sorted suffix array. O(n log n)
#define rep(i, a, b) for (int i = a; i < (b); i++)
    vector<int> sa, lcp;
    SuffixArray(string &s, int lim = 256) { // no null characters, use basic_string<int> to extend
        int n = s.size() + 1, k = 0, a, b;
        vector<int> x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
        sa = lcp = y, iota(all(sa), 0);
        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
            p = j, iota(all(y), n - j);
            rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;

Chillee

int gauss(vector<vector<double>> a, vector<double> &ans) {
    const double EPS = 1e-6;
    int n = (int)a.size();
    int m = (int)a[0].size() - 1;

    vector<int> where(m, -1);
    for (int col = 0, row = 0; col < m && row < n; ++col) {
        int sel = row;
        for (int i = row; i < n; ++i)
            if (abs(a[i][col]) > abs(a[sel][col]))