Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
2016/1/31
他人に読まれることを想定していない
#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;
}
#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))); }
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;
}
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;
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment