Competitive Programming Template for C++

bit.cpp

/// --- BIT Library --- ///

template<int SIZE, typename T = ll>
struct BIT{
	T data[SIZE+1];
	int n = SIZE;

	BIT(){
		REP(i, n+1) data[i] = 0;
	}

	void add(int i, T x) {
		i++;
		while(i<=n){
			data[i] += x;
			i += i&-i;
		}
	}
	ll sum(int i) {
		if(i<0) return 0;
		i++;
		ll s = 0;
		while(i>0){
			s += data[i];
			i -= i&-i;
		}
		return s;
	}
	ll range(int a, int b) {
		return sum(b) - sum(a-1);
	}
};

/// ------ ///

isPrime.cpp

/// --- Prime Library --- ///

bool isPrime(int n) {
	if(n < 2) return false;
	for(int i=2;i*i<=n;i++) {
		if(n%i == 0) return false;
	}
	return true;
}

/// ------ ///

marathon-time.cpp

#include <stdio.h>
#include <sys/time.h>

//

#define get_elapsed_time(begin, end) ((end.tv_sec - begin.tv_sec) * 1000\
  + (end.tv_usec - begin.tv_usec) / 1000.0);
stack<timeval> timeStack;
void pushTime(){
  timeval t;
  gettimeofday(&t, NULL);
  timeStack.push(t);
}
void popTime(string label = ""){
  timeval t1, t2;
  gettimeofday(&t2, NULL);
  t1 = timeStack.top();
  timeStack.pop();
  double mili = get_elapsed_time(t1, t2);
  label = "[" + label + "] ";
  cerr << label << mili << " milisec" << endl;
}

modbit.cpp

/// --- MODBIT Library --- ///
// depends on MOD

template<int SIZE>
struct MODBIT{
	int data[SIZE+1];
	int n = SIZE;

	BIT(){
		REP(i, n+1) data[i] = 0;
	}

	void add(int i, T x) {
		i++;
		while(i<=n){
			sadd(data[i], x);
			i += i&-i;
		}
	}
	int sum(int i) {
		if(i<0) return 0;
		i++;
		ll s = 0;
		while(i>0){
			sadd(s, data[i]);
			i -= i&-i;
		}
		return s;
	}
	int range(int a, int b) {
		return modadd(sum(b), -sum(a-1));
	}
};

/// ------ ///

mods.cpp

/// --- MOD Library --- ///
// N

int modadd(int a, int b) { return (((a + b) % MOD ) + MOD ) % MOD; }
void sadd(int &a, int b) { a = modadd(a, b); }
int modmul(int a, int b) { return (ll) a * b % MOD; }
void smul(int &a, int b) { a = modmul(a, b); }
int pow(int a, ll b) {
	int res = 1;
	while(b){
		if(b & 1) smul(res, a);
		smul(a, a);
	}
	return res;
}
int inv(int a) {
	return pow(a, MOD - 2);
}

int fact[N], invFact[N];

void initFactorial() {
	fact[0] = 1;
	FOR(i, 1, N) fact[i] = mul(fact[i - 1], i);
	invFact[N-1] = inv(fact[N - 1]);
	RREP(i, N-1) invFact[i] = mul(invFact[i + 1], i + 1);
}

int C(int n, int r) {
	return mul(fact[n], mul(invFact[r], invFact[n - r]));
}

/// ------ ///

seg.cpp

/// --- SegmentTree Library --- ///

template <typename T> function<T(T,T)> constexpr mmin(){ return [](T x, T y){return x<y?x:y;}; }
template <typename T> function<T(T,T)> constexpr mmax(){ return [](T x, T y){return x>y?x:y;}; }
template <typename T> function<T(T,T)> constexpr madd(){ return [](T x, T y){return x+y;}; }

template<typename T, int SIZE, T DEF, function<T(T,T)> &FUNC>
struct SegTree{
	T data[SIZE*4];
	int m;
	T def = DEF;
	function<T(T,T)> func = FUNC;
	SegTree(){
		m=1;
		while(m<SIZE) m<<=1;
		REP(i, m*2-1) data[i] = def;
	}
	void update(int i, T x) {
		i += m-1;
		data[i] = x;
		while(i>0) {
			i = (i-1)>>1;
			data[i] = func(data[i*2+1], data[i*2+2]);
		}
	}
	T query(int a, int b, int k=0,int l=0, int r=-1){
		if(r<0) r=m;
		if(b<=l||r<=a) return def;
		if(a<=l&&r<=b) return data[k];
		return func(
				query(a, b, k*2+1, l, (l+r)/2),
				query(a, b, k*2+2, (l+r)/2, r)
			);
	}
	T get(int i) {
		return data[i + m - 1];
	}
	void dum(int l = -1, int r = -1) {
		if(!DEBUG) return;
		if(l<0) l = 0;
		if(r<0) r = m;
		l = max(0, l);
		r = min(m, r);
		cerr<<l<<"[";
		FOR(i, l, r) {
			cerr<<get(i)<<(i!=r-1?", ":"");
		}
		cerr<<"]"<<r<<endl;
	}
};

auto imin = mmin<int>();

using RMQ = SegTree<int, N,  INF, imin>;
RMQ tree;

/// ------ ///

temp.cpp

// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
const bool DEBUG = 1;
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>
#include <cassert>
#include <functional>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = tuple<ll, ll>;
using P3 = tuple<ll, ll, ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VP = vector<P>;
using VS = vector<string>;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define FORI(i,a,b) for(int i=int(a);i<=int(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPI(i,n) FORI(i,0,n)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define RFORI(i,a,b) for(int i=int(b);i>=int(a);--i)
#define RREP(i,n) RFOR(i,0,n)
#define RREPI(i,n) RFORI(i,0,n)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique(ALL(a)),(a).end())
#define PB push_back
#define EACH(i,c) REP(i,(c).size())
#define REACH(i,c) RREP(i,(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))

#define BR cout<<"\n";

#define dump(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)<<"\n";
#define dump2(x,y) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<#x<<"="<<(x)\
  <<" , "<<#y<<"="<<(y)<<"\n";
#define dump3(x,y,z) if(DEBUG)cerr<<"["<<__LINE__<<"] "<<#x<<"="<<(x)\
  <<" , "<<#y<<"="<<(y)\
  <<" , "<<#z<<"="<<(z)<<"\n";

#define SAY(x) if(DEBUG) cerr<<"["<<__LINE__<< "] "<<(x)<<"\n";

#define YES(x) cout<<((x)?"YES":"NO")<<"\n";
#define Yes(x) cout<<((x)?"Yes":"No")<<"\n";
#define yes(x) cout<<((x)?"yes":"no")<<"\n";

inline int omajinai_int_in(){omajinai;int n;cin>>n;return n;}
inline ll omajinai_ll_in(){omajinai;ll n;cin>>n;return n;}
inline string omajinai_string_in(){omajinai;string n;cin>>n;return n;}
inline int int_in(){int n;cin>>n;return n;}
inline ll ll_in(){ll n;cin>>n;return n;}
inline string string_in(){string n;cin>>n;return n;}
#define oini omajinai_int_in()
#define oinl omajinai_ll_in()
#define oins omajinai_string_in()
#define ini int_in()
#define inl ll_in()
#define ins string_in()

#define isInside(y,x) (0<=(y)&&(y)<h&&0<=(x)&&(x)<w)

#define fi(x) (get<0>(x))
#define se(x) (get<1>(x))
#define th(x) (get<2>(x))
#define fo(x) (get<3>(x))
#define fif(x) (get<4>(x))

template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; EACH(i, v) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }

constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr int MOD = 1e9+7;

template <typename T> inline void smax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void smin(T &a, T b) { a = a < b ? a : b; }

ll ans;

int main() {
	//#####//
	
}

//