#include #include #include #include // Pythonのdictに相当 #include #include #include #include #include #include // std::setprecision // C++の競プロ用標準テンプレート using namespace std; // 型エイリアス using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vll = vector; // 定数 const ll mod = 998244353; const ll inf = 1001001001001001001LL; /* Pythonのdictを使った疎な2D BITをC++に移植します。 std::vector> を使用するのが Pythonの [dict() for _ in range(h + 1)] に最も近いです。 */ class BIT2D { private: int h, w; // data[i] が Python の self.data[i] (dict) に対応 vector> data; public: // コンストラクタ BIT2D(int h, int w) : h(h), w(w) { data.resize(h + 1); } /** * @brief 点(i, j)に値xを加算する (0-indexed) * @param i y座標 * @param j x座標 * @param x 加算する値 */ void add(int i, int j, ll x) { i++; // 1-indexedに変換 for (; i <= h; i += i & -i) { auto& bit = data[i]; // 該当するy座標のunordered_mapを取得 int k = j + 1; // 1-indexedに変換 for (; k <= w; k += k & -k) { bit[k] += x; // mapのキーkにxを加算 (キーがなければ自動で0に初期化) } } } /** * @brief 矩形領域 [0, i-1] x [0, j-1] の和を求める (0-indexed) * @param i y座標 (半開区間) * @param j x座標 (半開区間) * @return ll 矩形領域の和 */ ll prod(int i, int j) { ll res = 0; for (; i > 0; i -= i & -i) { // Pythonの if len(self.data[i]): と同じ if (data[i].empty()) continue; auto& bit = data[i]; int k = j; for (; k > 0; k -= k & -k) { // Pythonの if k in bit: と同じ auto it = bit.find(k); if (it != bit.end()) { res += it->second; // bit[k] の値 } } } return res; } }; int main() { // C++の入出力高速化 ios_base::sync_with_stdio(false); cin.tie(NULL); int lim = 1000000; int n; cin >> n; // Pythonの lim に合わせて初期化 BIT2D bit(lim, lim); ll ans = 0; for (int i = 0; i < n; ++i) { int l, r; cin >> l >> r; // Pythonの bit.prod(l, lim - r) ans += bit.prod(l, lim - r); // Pythonの bit.add(l, lim - r, 1) bit.add(l, lim - r, 1); } cout << ans << "\n"; return 0; }