/* -*- coding: utf-8 -*- * * 743.cc: No.743 Segments on a Polygon - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_M = 200000; /* typedef */ typedef long long ll; typedef pair pii; template struct BIT { int n; T bits[MAX_N + 1]; BIT() {} void init(int _n) { n = _n; memset(bits, 0, sizeof(bits)); } T sum(int x) { T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { while (x <= n) { bits[x] += v; x += (x & -x); } } }; /* global variables */ BIT bit; pii rs[MAX_N]; /* subroutines */ /* main */ int main() { int n, m; scanf("%d%d", &n, &m); bit.init(m + 1); for (int i = 0; i < n; i++) scanf("%d%d", &rs[i].first, &rs[i].second); sort(rs, rs + n); ll sum = 0; for (int i = 0; i < n; i++) { int a = rs[i].first, b = rs[i].second; if (a > b) swap(a, b); a++, b++; int d = bit.sum(b) - bit.sum(a); sum += d; //for (int i = 1; i <= m; i++) printf("%d ", bit.sum(i)); //printf("%d-%d: d=%d\n", a, b, d); bit.add(b, 1); } printf("%lld\n", sum); return 0; }