# Common Template

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

int main(void) {
    // code here
}

# Libraries

# Stack

O(1): int size()
O(1): T top()
O(1): void pop()
O(1): push(T x)
O(1): bool empty()

# Queue

O(1): int size()
O(1): T front()
O(1): void pop()
O(1): push(T x)
O(1): bool empty()

# Vector

O(1): int size()
O(1): v[i] O(1)
O(1): void push_back(T x)
O(1): void pop_back()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(n): void insert(int p, T x)
O(n): void erase(int p)
O(n): void clear()

# List

int size()
O(1): void push_back(T x)
O(1): void pop_back()
O(1): void push_front(T x)
O(1): void pop_front()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(1): void insert(int p, T x)
O(1): void erase(int p)
O(n): void clear()

# Set

set<T> S
O(1): int size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert(T key)
O(logn): void erase(T key)
O(logn): iterator<T> find(T key)
// ----
S.find(10) == S.end()

# Map

map<T1, T2> M
O(1): size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert((T1 key, T2 value))
O(logn): void erase(T1 key)
O(logn): iterator<T> find(T1 key)
O(logn): M[T1 key]
// ----
T["hoge"] = 1
T.insert(make_pair("key", 100))
pair<string, int> target = *T.find("key")
target.first
target.second

# Snippets

# Iternate over a container

You could use this style to avoid wrong index accesing.

vector<int> vec;
for (auto el: vec) {
    cout << el << endl;
};

for (auto it = vec.begin(); it != vec.end(); it++) {
    cout << *it << endl;
};

# Comparator for sorting

Comparator should return true, if a should proceed to b.
Otherwise return false.

The example below shows how to sort pairs of integers.
First, compare their first elements and then compare their second elements if the first elements don't help.

bool compare (pair<Int, Int> a, pair<Int, Int> b) {
  if (a.first != b.first)  return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  return false;
}

sort(items.begin(), items.end(), compare);

Template codes and libraries for competitive programming