結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2021-05-27 06:19:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 29,526 bytes |
コンパイル時間 | 3,006 ms |
コンパイル使用メモリ | 203,916 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-11-06 03:07:18 |
合計ジャッジ時間 | 5,608 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
// #pragma GCC optimize ("O3")// #pragma GCC target("avx512f")// #pragma GCC optimize("unroll-loops")// #ifndef ONLINE_JUDGE// #define _GLIBCXX_DEBUG// #endif#include<bits/stdc++.h>// #include <boost/multiprecision/cpp_dec_float.hpp>// #include <boost/multiprecision/cpp_int.hpp>// #include <boost/rational.hpp>// namespace mp = boost::multiprecision;// using Bint=mp::cpp_int;// using Real = mp::number<mp::cpp_dec_float<1024>>;// #include<atcoder/all>using namespace std;#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/#define pb push_back#define pf push_front#define fi first#define se second#define eb emplace_back// #define endl '\n'#define SZ(x) ((int)(x).size())#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define PI 3.14159265359const double eps = 1e-12;const long long INF= (long long)1e18+20;const int inf= 1010101010;typedef long double D; // 座標値の型。doubleかlong doubleを想定typedef complex<D> Point; // Pointtypedef long long ll;typedef vector<ll> vl;typedef vector<vl>vvl;typedef vector<vvl>vvvl;typedef vector<vvvl>vvvvl;typedef vector<vvvvl>vvvvvl;typedef vector<int>vi;typedef vector<vi>vvi;typedef vector<vvi>vvvi;typedef vector<vvvi>vvvvi;typedef vector<vvvvi>vvvvvi;typedef pair<ll,ll> P;// typedef double D;template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>;const ll MOD=1000000007LL;// const ll MOD=998244353LL;const ll mod=MOD;vl dx={0,0,1,-1,1,1,-1,-1};vl dy={1,-1,0,0,-1,1,-1,1};template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}//素因数分解O(√n)map<ll,ll>prime_factor(ll n){map<ll,ll>res;for(ll i=2;i*i<=n;i++){while(n%i==0){res[i]++;n/=i;}}if(n!=1)res[n]=1;return res;}const ll MAX = 5000010;long long fac[MAX], finv[MAX], inv[MAX];//finvが階乗の逆元// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}ll modpow(ll a, ll n,ll mod=MOD) {ll res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}/*Eratosthenes()ll N=2000010;vl arr(N);void Eratosthenes(){for(ll i = 0; i < N; i++){arr[i] = 1;}arr[1]=0;for(ll i = 2; i < sqrt(N); i++){if(arr[i]){for(ll j = 0; i * (j + 2) < N; j++){arr[i *(j + 2)] = 0;}}}}*///素数判定O(√n)bool is_prime(ll n){for(ll i=2;i*i<=n;i++){if(n%i==0)return false;}return n!=1;}//約数の列挙O(√n)vector<ll>divisor(ll n){vector<ll>res;for(ll i=1;i*i<=n;i++){if(n%i==0){res.push_back(i);if(i != n/i) res.push_back(n/i);}}return res;}/* Trie 木: 文字の種類(char_size)、int型で0に対応する文字(base)insert(word): 単語 word を Trie 木に挿入するsearch(word): 単語 word が Trie 木にあるか判定するstart_with(prefix): prefix が一致する単語が Trie 木にあるか判定するcount(): 挿入した単語の数を返すsize(): Trie 木の頂点数を返す計算量:insert, search ともに O(M)(Mは単語の長さ)*/template <int char_size, int base>struct Trie {struct Node { // 頂点を表す構造体vector<int> next; // 子の頂点番号を格納。存在しなければ-1vector<int> accept; // 末端がこの頂点になる単語の word_id を保存int c; // base からの間隔をint型で表現したものint common; // いくつの単語がこの頂点を共有しているかNode(int c_) : c(c_), common(0) {next.assign(char_size, -1);}};vector<Node> nodes; // trie 木本体int root;Trie() : root(0) {nodes.push_back(Node(root));}// 単語の挿入void insert(const string &word, int word_id) {int node_id = 0;for (int i = 0; i < (int)word.size(); i++) {int c = (int)(word[i] - base);int &next_id = nodes[node_id].next[c];if (next_id == -1) { // 次の頂点が存在しなければ追加next_id = (int)nodes.size();nodes.push_back(Node(c));}++nodes[node_id].common;node_id = next_id;}++nodes[node_id].common;nodes[node_id].accept.push_back(word_id);}void insert(const string &word) {insert(word, nodes[0].common);}// 単語とprefixの検索bool search(const string &word, bool prefix = false) {int node_id = 0;for (int i = 0; i < (int)word.size(); i++) {int c = (int)(word[i] - base);int &next_id = nodes[node_id].next[c];if (next_id == -1) { // 次の頂点が存在しなければ終了return false;}node_id = next_id;}return (prefix) ? true : nodes[node_id].accept.size() > 0;}// prefix を持つ単語が存在するかの検索bool start_with(const string &prefix) {return search(prefix, true);}// 挿入した単語の数int count() const {return (nodes[0].common);}// Trie木のノード数int size() const {return ((int)nodes.size());}};// //Lowest Common Ancestor// struct Edge{// int to;// Edge(int to):to(to){}// };// using Graph = vector<vector<Edge>>;// class lca {// public:// const int n = 0;// const int log2_n = 0;// vector<vector<int>> parent;// vector<int> depth;// lca() {}// //g:グラフ root:根// lca(const Graph &g, int root)// : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector<int>(n)), depth(n) {// dfs(g, root, -1, 0);// for (int k = 0; k + 1 < log2_n; k++) {// for (int v = 0; v < (int)g.size(); v++) {// if (parent[k][v] < 0)// parent[k + 1][v] = -1;// else// parent[k + 1][v] = parent[k][parent[k][v]];// }// }// }// void dfs(const Graph &g, int v, int p, int d) {// parent[0][v] = p;// depth[v] = d;// for (auto &e : g[v]) {// if (e.to != p) dfs(g, e.to, v, d + 1);// }// }// //uとvのlcaを取得// int get(int u, int v) {// if (depth[u] > depth[v]) swap(u, v);// for (int k = 0; k < log2_n; k++) {// if ((depth[v] - depth[u]) >> k & 1) {// v = parent[k][v];// }// }// if (u == v) return u;// for (int k = log2_n - 1; k >= 0; k--) {// if (parent[k][u] != parent[k][v]) {// u = parent[k][u];// v = parent[k][v];// }// }// return parent[0][u];// }// int dep(int i) {// return depth[i];// }// int dist(int u,int v){// return depth[u]+depth[v]-depth[get(u,v)]*2;// }// };// union by size + path havingclass UnionFind {public:vector <ll> par; // 各元の親を表す配列vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)// ConstructorUnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかったfor (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}// Member Function// Findll root(ll x) { // 根の検索while (par[x] != x) {x = par[x] = par[par[x]]; // x の親の親を x の親とする}return x;}// Union(Unite, Merge)bool merge(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;// merge technique(データ構造をマージするテク.小を大にくっつける)if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(ll x, ll y) { // 連結判定return root(x) == root(y);}ll size(ll x) { // 素集合のサイズreturn siz[root(x)];}};// 0-indexed parmutation onlyvvl cycle_partition(const vl &p){ll n=p.size();vvl ret;vector<bool> check(n,false);rep(i,n)if(!check[p[i]]){vl v;ll pos=p[i];v.pb(i);check[i]=true;while(pos!=i){v.pb(pos);check[pos]=true;pos=p[pos];}ret.pb(v);}return ret;}vl Z_algorithm(vl s){ll c=0,n=s.size();vl Z(n,0);for(ll i=1;i<n;i++){ll l=i-c;if(i+Z[l]<c+Z[c]){Z[i]=Z[l];}else{ll j=max(0LL,c+Z[c]-i);while(i+j<n && s[j]==s[i+j])j++;Z[i]=j;c=i;}}Z[0]=n;return Z;}//Manachar 修理中// vl Manachar(string S){// ll c=0,n=S.size();// vl R(n,1);// for(ll i=0;i<n;i++){// ll l=c-(i-c);// if(i+R[l]<c+R[c]){// R[i]=R[l];// }else{// ll j=c+R[c]-i;// while(i-j>=0 && i+j<n && S[i-j] == S[i+j])j++;// R[i]=j;// c=i;// }// }// return R;// }template <typename T>T pow(T a, long long n, T e = 1) {T ret = e;while (n) {if (n & 1) ret *= a;a *= a;n >>= 1;}return ret;}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long x_) {if ((x = x_ % mod + mod) >= mod) x -= mod;}ModInt& operator+=(ModInt rhs) {if ((x += rhs.x) >= mod) x -= mod;return *this;}ModInt& operator-=(ModInt rhs) {if ((x -= rhs.x) < 0) x += mod;return *this;}ModInt& operator*=(ModInt rhs) {x = (unsigned long long)x * rhs.x % mod;return *this;}ModInt& operator/=(ModInt rhs) {x = (unsigned long long)x * rhs.inv().x % mod;return *this;}ModInt operator-() const { return -x < 0 ? mod - x : -x; }ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }bool operator==(ModInt rhs) const { return x == rhs.x; }bool operator!=(ModInt rhs) const { return x != rhs.x; }ModInt inv() const { return pow(*this, mod - 2); }friend ostream& operator<<(ostream& s, ModInt<mod> a) {s << a.x;return s;}friend istream& operator>>(istream& s, ModInt<mod>& a) {s >> a.x;return s;}};using mint = ModInt<MOD>;typedef vector<mint> vm;typedef vector<vector<mint> >vvm;typedef vector<vector<vector<mint> > >vvvm;template <typename T>struct segment_tree_beats{int N;vector<T> max1, max2, min1, min2, add, sum;vector<int> maxc, minc, len;void update_max(int i, T x){sum[i] += (x - max1[i]) * maxc[i];if (max1[i] == min1[i]){min1[i] = x;} else if (max1[i] == min2[i]){min2[i] = x;}max1[i] = x;}void update_min(int i, T x){sum[i] += (x - min1[i]) * minc[i];if (min1[i] == max1[i]){max1[i] = x;} else if (min1[i] == max2[i]){max2[i] = x;}min1[i] = x;}void update_add(int i, T x){max1[i] += x;if (max2[i] != -INF){max2[i] += x;}min1[i] += x;if (min2[i] != INF){min2[i] += x;}sum[i] += x * len[i];add[i] += x;}void push(int i){if (i >= N - 1){return;}int l = i * 2 + 1;int r = i * 2 + 2;if (add[i] != 0){update_add(l, add[i]);update_add(r, add[i]);add[i] = 0;}if (max1[i] < max1[l]){update_max(l, max1[i]);}if (min1[i] > min1[l]){update_min(l, min1[i]);}if (max1[i] < max1[r]){update_max(r, max1[i]);}if (min1[i] > min1[r]){update_min(r, min1[i]);}}void update(int i){int l = i * 2 + 1;int r = i * 2 + 2;sum[i] = sum[l] + sum[r];if (max1[l] > max1[r]){max1[i] = max1[l];max2[i] = max(max2[l], max1[r]);maxc[i] = maxc[l];} else if (max1[l] < max1[r]){max1[i] = max1[r];max2[i] = max(max1[l], max2[r]);maxc[i] = maxc[r];} else {max1[i] = max1[l];max2[i] = max(max2[l], max2[r]);maxc[i] = maxc[l] + maxc[r];}if (min1[l] < min1[r]){min1[i] = min1[l];min2[i] = min(min2[l], min1[r]);minc[i] = minc[l];} else if (min1[l] > min1[r]){min1[i] = min1[r];min2[i] = min(min1[l], min2[r]);minc[i] = minc[r];} else {min1[i] = min1[l];min2[i] = min(min2[l], min2[r]);minc[i] = minc[l] + minc[r];}}segment_tree_beats(vector<T> A){int n = A.size();N = 1;while (N < n){N *= 2;}max1 = vector<T>(N * 2 - 1, -INF);max2 = vector<T>(N * 2 - 1, -INF);min1 = vector<T>(N * 2 - 1, INF);min2 = vector<T>(N * 2 - 1, INF);add = vector<T>(N * 2 - 1, 0);sum = vector<T>(N * 2 - 1, 0);maxc = vector<int>(N * 2 - 1, 1);minc = vector<int>(N * 2 - 1, 1);len = vector<int>(N * 2 - 1, 1);for (int i = 0; i < n; i++){max1[N - 1 + i] = A[i];min1[N - 1 + i] = A[i];sum[N - 1 + i] = A[i];}for (int i = N - 2; i >= 0; i--){len[i] = len[i * 2 + 1] + len[i * 2 + 2];update(i);}}void range_chmin(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l || x >= max1[i]){return;} else if (L <= l && r <= R && x > max2[i]){update_max(i, x);return;}push(i);int m = (l + r) / 2;range_chmin(L, R, x, i * 2 + 1, l, m);range_chmin(L, R, x, i * 2 + 2, m, r);update(i);}void range_chmax(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l || x <= min1[i]){return;} else if (L <= l && r <= R && x < min2[i]){update_min(i, x);return;}push(i);int m = (l + r) / 2;range_chmax(L, R, x, i * 2 + 1, l, m);range_chmax(L, R, x, i * 2 + 2, m, r);update(i);}void range_add(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l){return;} else if (L <= l && r <= R){update_add(i, x);return;}push(i);int m = (l + r) / 2;range_add(L, R, x, i * 2 + 1, l, m);range_add(L, R, x, i * 2 + 2, m, r);update(i);}T range_sum(int L, int R, int i, int l, int r){if (r <= L || R <= l){return 0;} else if (L <= l && r <= R){return sum[i];}push(i);int m = (l + r) / 2;return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r);}void range_chmin(int L, int R, T x){range_chmin(L, R, x, 0, 0, N);}void range_chmax(int L, int R, T x){range_chmax(L, R, x, 0, 0, N);}void range_add(int L, int R, T x){range_add(L, R, x, 0, 0, N);}T range_sum(int L, int R){return range_sum(L, R, 0, 0, N);}};struct PartiallyPersistentUnionFind {vector<ll> par, last;vector<vector<P> > history;PartiallyPersistentUnionFind(ll n) : par(n, -1), last(n, -1), history(n) {for (auto &vec : history) vec.emplace_back(-1, -1);}void init(ll n) {par.assign(n, -1); last.assign(n, -1); history.assign(n, vector<P>());for (auto &vec : history) vec.emplace_back(-1, -1);}ll root(ll t, ll x) {if (last[x] == -1 || t < last[x]) return x;return root(t, par[x]);}bool issame(ll t, ll x, ll y) {return root(t, x) == root(t, y);}bool merge(ll t, ll x, ll y) {x = root(t, x); y = root(t, y);if (x == y) return false;if (par[x] > par[y]) swap(x, y); // merge techniquepar[x] += par[y];par[y] = x;last[y] = t;history[x].emplace_back(t, par[x]);return true;}ll size(ll t, ll x) {x = root(t, x);return -prev(lower_bound(history[x].begin(), history[x].end(), make_pair(t, 0LL)))->second;}};// matrix// template<class T> struct Matrix {// vector<vector<T> > val;// Matrix(int n = 1, int m = 1, T v = 0) : val(n, vector<T>(m, v)) {}// void init(int n, int m, T v = 0) {val.assign(n, vector<T>(m, v));}// void resize(int n, int m) {// val.resize(n);// for (int i = 0; i < n; ++i) val[i].resize(m);// }// Matrix<T>& operator = (const Matrix<T> &A) {// val = A.val;// return *this;// }// size_t size() const {return val.size();}// vector<T>& operator [] (int i) {return val[i];}// const vector<T>& operator [] (int i) const {return val[i];}// friend ostream& operator << (ostream& s, const Matrix<T>& M) {// s << endl;// for (int i = 0; i < (int)M.size(); ++i) s << M[i] << endl;// return s;// }// };// template<class T> Matrix<T> operator * (const Matrix<T> &A, const Matrix<T> &B) {// Matrix<T> R(A.size(), B[0].size());// for (int i = 0; i < A.size(); ++i)// for (int j = 0; j < B[0].size(); ++j)// for (int k = 0; k < B.size(); ++k)// R[i][j] += A[i][k] * B[k][j];// return R;// }// template<class T> Matrix<T> pow(const Matrix<T> &A, long long n) {// Matrix<T> R(A.size(), A.size());// auto B = A;// for (int i = 0; i < A.size(); ++i) R[i][i] = 1;// while (n > 0) {// if (n & 1) R = R * B;// B = B * B;// n >>= 1;// }// return R;// }// template<class T> vector<T> operator * (const Matrix<T> &A, const vector<T> &B) {// vector<T> v(A.size());// for (int i = 0; i < A.size(); ++i)// for (int k = 0; k < B.size(); ++k)// v[i] += A[i][k] * B[k];// return v;// }// template<class T> Matrix<T> operator + (const Matrix<T> &A, const Matrix<T> &B) {// Matrix<T> R(A.size(), A[0].size());// for (int i = 0; i < A.size(); ++i)// for (int j = 0; j < A[0].size(); ++j)// R[i][j] = A[i][j] + B[i][j];// return R;// }// template<class T> Matrix<T> operator - (const Matrix<T> &A, const Matrix<T> &B) {// Matrix<T> R(A.size(), A[0].size());// for (int i = 0; i < A.size(); ++i)// for (int j = 0; j < A[0].size(); ++j)// R[i][j] = A[i][j] - B[i][j];// return R;// }// const int MAX_ROW = 510; // to be set appropriately// const int MAX_COL = 510; // to be set appropriately// struct BitMatrix {// int H, W;// bitset<MAX_COL> val[MAX_ROW];// BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}// inline bitset<MAX_COL>& operator [] (int i) {return val[i];}// };// int GaussJordan(BitMatrix &A, bool is_extended = false) {// int rank = 0;// for (int col = 0; col < A.W; ++col) {// if (is_extended && col == A.W - 1) break;// int pivot = -1;// for (int row = rank; row < A.H; ++row) {// if (A[row][col]) {// pivot = row;// break;// }// }// if (pivot == -1) continue;// swap(A[pivot], A[rank]);// for (int row = 0; row < A.H; ++row) {// if (row != rank && A[row][col]) A[row] ^= A[rank];// }// ++rank;// }// return rank;// }// int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {// int m = A.H, n = A.W;// BitMatrix M(m, n + 1);// for (int i = 0; i < m; ++i) {// for (int j = 0; j < n; ++j) M[i][j] = A[i][j];// M[i][n] = b[i];// }// int rank = GaussJordan(M, true);// // check if it has no solution// for (int row = rank; row < m; ++row) if (M[row][n]) return -1;// // answer// res.assign(n, 0);// for (int i = 0; i < rank; ++i) res[i] = M[i][n];// return rank;// }ll exp(ll n,ll r){if(r==0)return 1;return n*exp(n,r-1);}ll factorial(int n){if(n==0)return 1;return n*factorial(n-1);}void input_vvi(int n){vector<string>s(n);string ans;ans+="vector<vector<int>> dp={";rep(i,n){cin>>s[i];ans+="{";ans+=s[i];ans+="}";if(i!=n-1)ans+=",";}ans+="};";cout<<ans<<endl;}/*** @brief Rolling-Hash(ローリングハッシュ)* @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6* @docs docs/rolling-hash.md*/struct RollingHash {static const uint64_t mod = (1ull << 61ull) - 1;using uint128_t = __uint128_t;vector< uint64_t > power;const uint64_t base;static inline uint64_t add(uint64_t a, uint64_t b) {if((a += b) >= mod) a -= mod;return a;}static inline uint64_t mul(uint64_t a, uint64_t b) {uint128_t c = (uint128_t) a * b;return add(c >> 61, c & mod);}static inline uint64_t generate_base() {mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1);return rand(mt);}inline void expand(size_t sz) {if(power.size() < sz + 1) {int pre_sz = (int) power.size();power.resize(sz + 1);for(int i = pre_sz - 1; i < sz; i++) {power[i + 1] = mul(power[i], base);}}}explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {}vector< uint64_t > build(const string &s) const {int sz = s.size();vector< uint64_t > hashed(sz + 1);for(int i = 0; i < sz; i++) {hashed[i + 1] = add(mul(hashed[i], base), s[i]);}return hashed;}template< typename T >vector< uint64_t > build(const vector< T > &s) const {int sz = s.size();vector< uint64_t > hashed(sz + 1);for(int i = 0; i < sz; i++) {hashed[i + 1] = add(mul(hashed[i], base), s[i]);}return hashed;}uint64_t query(const vector< uint64_t > &s, int l, int r) {expand(r - l);return add(s[r], mod - mul(s[l], power[r - l]));}uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {expand(h2len);return add(mul(h1, power[h2len]), h2);}int lcp(const vector< uint64_t > &a, int l1, int r1, const vector< uint64_t > &b, int l2, int r2) {int len = min(r1 - l1, r2 - l2);int low = 0, high = len + 1;while(high - low > 1) {int mid = (low + high) / 2;if(query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid;else high = mid;}return low;}};struct SuccinctIndexableDictionary {size_t length;size_t blocks;vector< unsigned > bit, sum;SuccinctIndexableDictionary() = default;SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {bit.assign(blocks, 0U);sum.assign(blocks, 0U);}void set(int k) {bit[k >> 5] |= 1U << (k & 31);}void build() {sum[0] = 0U;for(int i = 1; i < blocks; i++) {sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);}}bool operator[](int k) {return (bool((bit[k >> 5] >> (k & 31)) & 1));}int rank(int k) {return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));}int rank(bool val, int k) {return (val ? rank(k) : k - rank(k));}};/** @brief Wavelet-Matrix(ウェーブレット行列)* @docs docs/wavelet-matrix.md*/template< typename T, int MAXLOG >struct WaveletMatrix {size_t length;SuccinctIndexableDictionary matrix[MAXLOG];int mid[MAXLOG];WaveletMatrix() = default;WaveletMatrix(vector< T > v) : length(v.size()) {vector< T > l(length), r(length);for(int level = MAXLOG - 1; level >= 0; level--) {matrix[level] = SuccinctIndexableDictionary(length + 1);int left = 0, right = 0;for(int i = 0; i < length; i++) {if(((v[i] >> level) & 1)) {matrix[level].set(i);r[right++] = v[i];} else {l[left++] = v[i];}}mid[level] = left;matrix[level].build();v.swap(l);for(int i = 0; i < right; i++) {v[left + i] = r[i];}}}pair< int, int > succ(bool f, int l, int r, int level) {return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};}// v[k]T access(int k) {T ret = 0;for(int level = MAXLOG - 1; level >= 0; level--) {bool f = matrix[level][k];if(f) ret |= T(1) << level;k = matrix[level].rank(f, k) + mid[level] * f;}return ret;}T operator[](const int &k) {return access(k);}// count i s.t. (0 <= i < r) && v[i] == xint rank(const T &x, int r) {int l = 0;for(int level = MAXLOG - 1; level >= 0; level--) {tie(l, r) = succ((x >> level) & 1, l, r, level);}return r - l;}// k-th(0-indexed) smallest number in v[l,r)T kth_smallest(int l, int r, int k) {assert(0 <= k && k < r - l);T ret = 0;for(int level = MAXLOG - 1; level >= 0; level--) {int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);bool f = cnt <= k;if(f) {ret |= T(1) << level;k -= cnt;}tie(l, r) = succ(f, l, r, level);}return ret;}// k-th(0-indexed) largest number in v[l,r)T kth_largest(int l, int r, int k) {return kth_smallest(l, r, r - l - k - 1);}// count i s.t. (l <= i < r) && (v[i] < upper)int range_freq(int l, int r, T upper) {int ret = 0;for(int level = MAXLOG - 1; level >= 0; level--) {bool f = ((upper >> level) & 1);if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);tie(l, r) = succ(f, l, r, level);}return ret;}// count i s.t. (l <= i < r) && (lower <= v[i] < upper)int range_freq(int l, int r, T lower, T upper) {return range_freq(l, r, upper) - range_freq(l, r, lower);}// max v[i] s.t. (l <= i < r) && (v[i] < upper)T prev_value(int l, int r, T upper) {int cnt = range_freq(l, r, upper);return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);}// min v[i] s.t. (l <= i < r) && (lower <= v[i])T next_value(int l, int r, T lower) {int cnt = range_freq(l, r, lower);return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);}};template< typename T, int MAXLOG >struct CompressedWaveletMatrix {WaveletMatrix< int, MAXLOG > mat;vector< T > ys;CompressedWaveletMatrix(const vector< T > &v) : ys(v) {sort(begin(ys), end(ys));ys.erase(unique(begin(ys), end(ys)), end(ys));vector< int > t(v.size());for(int i = 0; i < v.size(); i++) t[i] = get(v[i]);mat = WaveletMatrix< int, MAXLOG >(t);}inline int get(const T& x) {return lower_bound(begin(ys), end(ys), x) - begin(ys);}T access(int k) {return ys[mat.access(k)];}T operator[](const int &k) {return access(k);}int rank(const T &x, int r) {auto pos = get(x);if(pos == ys.size() || ys[pos] != x) return 0;return mat.rank(pos, r);}T kth_smallest(int l, int r, int k) {return ys[mat.kth_smallest(l, r, k)];}T kth_largest(int l, int r, int k) {return ys[mat.kth_largest(l, r, k)];}int range_freq(int l, int r, T upper) {return mat.range_freq(l, r, get(upper));}int range_freq(int l, int r, T lower, T upper) {return mat.range_freq(l, r, get(lower), get(upper));}T prev_value(int l, int r, T upper) {auto ret = mat.prev_value(l, r, get(upper));return ret == -1 ? T(-1) : ys[ret];}T next_value(int l, int r, T lower) {auto ret = mat.next_value(l, r, get(lower));return ret == -1 ? T(-1) : ys[ret];}};int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(13);//CDEは制約を読もう!//主客転倒!二重和のときは一番内側の物が何回使われるか//√Nで分けるテク//絶対値は外して2通りの式にした後、変数ごとにまとめる//組み合わせが少ないそうなものはdfsで実行してみる(典型25)/*--------------------------------*/int n,m;cin>>n>>m;vector<P>vec(n);rep(i,n){cin>>vec[i].fi>>vec[i].se;if(vec[i].se<vec[i].fi)swap(vec[i].fi,vec[i].se);}sort(all(vec));vl b(n);rep(i,n)b[i]=vec[i].se;WaveletMatrix<ll,30>wm(b);ll ans=0;rep(i,n){ans+=wm.range_freq(0,i,vec[i].fi+1,vec[i].se);}cout<<ans<<endl;}