2016/1/31

競プロテンプレート

他人に読まれることを想定していない

base.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tmpA template<class A>
#define tmpAB template<class A, class B>

struct nout{ tmpA const nout& operator<<(const A& a) const { return *this; } } nout;
#ifdef EBUG
    #define ln << endl
    #define dout cout
#else
    #define ln << "\n"
    #define dout nout
#endif
#define IN(n) n; cin >> n;

#define times(n, i)       uptil(0, n, i)
#define rtimes(n, i)      downto((n) - 1, 0, i)
#define upto(f, t, i)     for(int i##__count = (f), i = i##__count, i##__goal = (t); i <= i##__goal; i = ++i##__count)
#define uptil(f, t, i)    for(int i##__count = (f), i = i##__count, i##__goal = (t); i <  i##__goal; i = ++i##__count)
#define downto(f, t, i)   for(int i##__count = (f), i = i##__count, i##__goal = (t); i >= i##__goal; i = --i##__count)
#define downtil(f, t, i)  for(int i##__count = (f), i = i##__count, i##__goal = (t); i >  i##__goal; i = --i##__count)
#define timesB(n, i)      uptilB(0, n, i)
#define rtimesB(n, i)     downtoB((n) - 1, 0, i)
#define uptoB(f, t, i)    for(int i = (f); i <= (t); ++i)
#define uptilB(f, t, i)   for(int i = (f); i <  (t); ++i)
#define downtoB(f, t, i)  for(int i = (f); i >= (t); --i)
#define downtilB(f, t, i) for(int i = (f); i >  (t); --i)

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    return 0;
}

collection.cpp

#define all(v) begin(v), end(v)
int sum_mod    (const vector<int>& v, int mod = LLONG_MAX) {
    int ans = 0;
    for(int x : v)
        ans = (ans + x) % mod;
    return ans;
}
int product_mod(const vector<int>& v, int mod = LLONG_MAX) {
    int ans = 1;
    for(int x : v)
        ans = (ans * x) % mod;
    return ans;
}
int min        (const vector<int>& v) { return *min_element(all(v)); }
int min_index  (const vector<int>& v) { return distance(begin(v), min_element(all(v))); }
int max        (const vector<int>& v) { return *max_element(all(v)); }
int max_index  (const vector<int>& v) { return distance(begin(v), max_element(all(v))); }

math.cpp

int prime_count;
int primes[1000000];
bool is_prime[1000001];
void calc_prime(int max) {
    upto(2, max, i) is_prime[i] = true;
    upto(2, max, i) {
        if(is_prime[i]) {
            primes[prime_count++] = i;
            upto(2, max / i, j) is_prime[i * j] = false;
        }
    }
}
int pow_mod(int x, int n, int mod) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = (ans * x) % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}
int div_modP(int d, int r, int modP) {
    return d * pow_mod(r, modP - 2, modP) % modP;
}

tree.cpp

class UnionFindTree {
    vector<int> parents;
    vector<int> ranks;
    int count;
public:
    UnionFindTree(int n) : parents(n), ranks(n, 0), count(n) {
        times(n, i) parents[i] = i;
    }
    int root(int i) { /* amortized cost: a(n) */
        if(parents[i] == i) {
            return i;
        } else {
            return parents[i] = root(parents[i]);
        }
    }
    bool merge(int a, int b) { /* amortized cost: a(n) */
        a = root(a);
        b = root(b);
        if(a == b) return false;
        count--;
        if(ranks[a] < ranks[b]) {
            parents[a] = b;
        } else {
            parents[b] = a;
            if(ranks[a] == ranks[b]) ranks[a]++;
        }
        return true;
    }
    bool same(int a, int b) { return root(a) == root(b); }
    int group_count() { return count; }
};
class BIT {
    vector<int> data; // 1-origin
public:
    BIT(int n) : data(n + 1, 0) {}
    int sum(int i) {
        ++i;
        int s = 0;
        while(i > 0) {
            s += data[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, int d) {
        ++i;
        while(i < data.size()) {
            data[i] += d;
            i += i & -i;
        }
    }
};