結果

問題 No.3313 Matryoshka
コンテスト
ユーザー rabimea
提出日時 2025-11-01 01:01:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,456 ms / 4,000 ms
コード長 1,473 bytes
コンパイル時間 3,724 ms
コンパイル使用メモリ 295,024 KB
実行使用メモリ 21,716 KB
最終ジャッジ日時 2025-11-01 01:02:07
合計ジャッジ時間 31,273 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
using std::cin, std::cout, std::cerr;
using ll = long long;

int LowBit(int x) { return x & (-x); }
struct BIT {
    int n;
    std::vector<int> a;
    BIT(int n) { Init(n); }
    void Init(int n) { this->n = n; a.assign(n + 1, 0); }

    void Update(int p, int x) {
        for(int i = p + 1; i <= n + 1; i += LowBit(i))
            a[i - 1] += x;
    }
    int Query(int p) {
        int r = 0;
        for(int i = p + 1; i; i -= LowBit(i))
            r += a[i - 1];
        return r;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    int n; cin >> n;
    std::vector<std::pair<int, int>> a(n);
    rep(i, 0, n - 1) {
        int l, r; cin >> l >> r;
        a[i] = {l, r};
    }

    ll ans = 0;
    int M = 1e6 + 1;
    BIT bit(M);
    std::function<void(int, int)> solve = [&](int l, int r) {
        if(l + 1 == r) return;
        int m = (l + r) / 2;
        solve(l, m);
        solve(m, r);

        std::vector<std::tuple<int, int, int>> b;
        rep(i, l, r - 1) b.push_back({a[i].first, a[i].second, i >= m});
        std::ranges::sort(b);

        for(auto [l, r, t] : b) {
            if(t == 0)
                bit.Update(r, 1);
            else
                ans += bit.Query(M) - bit.Query(r);
        }
        for(auto [l, r, t] : b) {
            if(t == 0)
                bit.Update(r, -1);
        }
    };
    solve(0, n);
    cout << ans << '\n';
}
0