結果

問題 No.3313 Matryoshka
コンテスト
ユーザー lif4635
提出日時 2025-10-24 22:32:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,858 bytes
コンパイル時間 1,205 ms
コンパイル使用メモリ 129,248 KB
実行使用メモリ 67,772 KB
最終ジャッジ日時 2025-10-24 22:32:31
合計ジャッジ時間 9,793 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map> // Pythonのdictに相当
#include <map>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <iomanip> // std::setprecision

// C++の競プロ用標準テンプレート
using namespace std;

// 型エイリアス
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

// 定数
const ll mod = 998244353;
const ll inf = 1001001001001001001LL;

/*
Pythonのdictを使った疎な2D BITをC++に移植します。
std::vector<std::unordered_map<int, long long>> を使用するのが
Pythonの [dict() for _ in range(h + 1)] に最も近いです。
*/

class BIT2D {
private:
    int h, w;
    // data[i] が Python の self.data[i] (dict) に対応
    vector<unordered_map<int, ll>> 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;
}
0