#1193431 (C++23(gcc16)) No.3313 Matryoshka

• 問題: No.3313 Matryoshka
• ユーザー: detteiuu
• 提出日時: 2026-10-17 06:29:59
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 8,936 bytes
• コンパイル時間: 8,485 ms
• コンパイル使用メモリ: 405,364 KB
• 実行使用メモリ: 133,376 KB
• 最終ジャッジ日時: 2026-10-17 06:31:07
• 合計ジャッジ時間: 66,828 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 18 WA * 17

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define repr2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define YesNo(cond) cout << ((cond) ? "Yes\n" : "No\n")
#define YESNO(cond) cout << ((cond) ? "YES\n" : "NO\n")

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

template <typename T> void print(const T& value) { cout << value << "\n"; }
template <typename T> void print(const vector<T>& vec) { for (auto& v : vec) cout << v << " "; cout << "\n"; }
template <typename T> void input(vector<T>& vec) { for (auto& v : vec) cin >> v; };
template <typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;

// https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
template<class T>
class SortedMultiset {
private:
    static constexpr int BUCKET_RATIO = 16;
    static constexpr int SPLIT_RATIO = 24;

    vector<vector<T>> a;
    int sz = 0;

    void build(const vector<T>& v) {
        int n = v.size();
        sz = n;
        if (n == 0) {
            a.clear();
            return;
        }

        int num_bucket = (int)ceil(sqrt((double)n / BUCKET_RATIO));
        a.resize(num_bucket);

        for (int i = 0; i < num_bucket; i++) {
            int l = n * i / num_bucket;
            int r = n * (i + 1) / num_bucket;
            a[i] = vector<T>(v.begin() + l, v.begin() + r);
        }
    }

    pair<int,int> position(const T& x) const {
        // return {bucket index, position in bucket}
        for (int i = 0; i < (int)a.size(); i++) {
            if (x <= a[i].back()) {
                return {i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin()};
            }
        }

        int i = (int)a.size() - 1;
        return {i, (int)a[i].size()};
    }

    T pop_internal(int b, int i) {
        T ans = a[b][i];
        a[b].erase(a[b].begin() + i);
        sz--;

        if (a[b].empty()) {
            a.erase(a.begin() + b);
        }

        return ans;
    }

public:
    SortedMultiset() {}

    SortedMultiset(vector<T> v) {
        sort(v.begin(), v.end());
        build(v);
    }

    int size() const {
        return sz;
    }

    bool empty() const {
        return sz == 0;
    }

    bool contains(const T& x) const {
        if (sz == 0) return false;

        auto [b, i] = position(x);

        return i < (int)a[b].size() && a[b][i] == x;
    }

    int count(const T& x) const {
        return index_right(x) - index(x);
    }

    void add(const T& x) {
        if (sz == 0) {
            a = {{x}};
            sz = 1;
            return;
        }

        auto [b, i] = position(x);

        a[b].insert(a[b].begin() + i, x);
        sz++;

        if ((int)a[b].size() > (int)a.size() * SPLIT_RATIO) {
            int mid = a[b].size() >> 1;

            vector<T> left(a[b].begin(), a[b].begin() + mid);
            vector<T> right(a[b].begin() + mid, a[b].end());

            a.erase(a.begin() + b);
            a.insert(a.begin() + b, right);
            a.insert(a.begin() + b, left);
        }
    }

    bool discard(const T& x) {
        if (sz == 0) return false;

        auto [b, i] = position(x);

        if (i == (int)a[b].size() || a[b][i] != x) {
            return false;
        }

        pop_internal(b, i);
        return true;
    }

    optional<T> lt(const T& x) const {
        for (int i = (int)a.size() - 1; i >= 0; i--) {
            if (a[i][0] < x) {
                auto it = lower_bound(a[i].begin(), a[i].end(), x);
                --it;
                return *it;
            }
        }
        return nullopt;
    }

    optional<T> le(const T& x) const {
        for (int i = (int)a.size() - 1; i >= 0; i--) {
            if (a[i][0] <= x) {
                auto it = upper_bound(a[i].begin(), a[i].end(), x);
                --it;
                return *it;
            }
        }
        return nullopt;
    }

    optional<T> gt(const T& x) const {
        for (int i = 0; i < (int)a.size(); i++) {
            if (a[i].back() > x) {
                auto it = upper_bound(a[i].begin(), a[i].end(), x);
                return *it;
            }
        }
        return nullopt;
    }

    optional<T> ge(const T& x) const {
        for (int i = 0; i < (int)a.size(); i++) {
            if (a[i].back() >= x) {
                auto it = lower_bound(a[i].begin(), a[i].end(), x);
                return *it;
            }
        }
        return nullopt;
    }

    T operator[](int i) const {
        if (i < 0) i += sz;

        for (auto &bucket : a) {
            if (i < (int)bucket.size()) {
                return bucket[i];
            }
            i -= bucket.size();
        }

        throw out_of_range("index out of range");
    }

    T pop(int i = -1) {
        if (i < 0) i += sz;

        for (int b = 0; b < (int)a.size(); b++) {
            if (i < (int)a[b].size()) {
                return pop_internal(b, i);
            }
            i -= a[b].size();
        }

        throw out_of_range("index out of range");
    }

    int index(const T& x) const {
        int ans = 0;

        for (auto &bucket : a) {
            if (bucket.back() >= x) {
                return ans + (lower_bound(bucket.begin(), bucket.end(), x) - bucket.begin());
            }
            ans += bucket.size();
        }

        return ans;
    }

    int index_right(const T& x) const {
        int ans = 0;

        for (auto &bucket : a) {
            if (bucket.back() > x) {
                return ans + (upper_bound(bucket.begin(), bucket.end(), x) - bucket.begin());
            }
            ans += bucket.size();
        }

        return ans;
    }

    vector<T> to_vector() const {
        vector<T> res;

        for (auto &bucket : a) {
            for (auto &x : bucket) {
                res.push_back(x);
            }
        }

        return res;
    }
};

struct BITSortedMultiset {
    int N;
    vector<SortedMultiset<ll>> bit;

    BITSortedMultiset(int N)
        : N(N) {
        bit.assign(N+1, SortedMultiset<ll> ());
    }

    void insert(int p, ll x) {
        for (int i = p+1; i <= N; i += i&-i) {
            bit[i].add(x);
        }
    }

    void remove(int p, ll x) {
        for (int i = p+1; i <= N; i += i&-i) {
            bit[i].discard(x);
        }
    }

    // [0,r) 内の x以上の個数
    ll prefix_count_ge(int r, ll x) const {
        ll ans = 0;

        for (int i = r; i > 0; i -= i&-i) {
            ans += bit[i].size() - bit[i].index(x);
        }

        return ans;
    }

    // [0,r) 内の x以下の個数
    ll prefix_count_le(int r, ll x) const {
        ll ans = 0;

        for (int i = r; i > 0; i -= i&-i) {
            ans += bit[i].index_right(x);
        }

        return ans;
    }

    // [0,r) 内の x以上y以下の個数
    ll prefix_count_range(int r, ll x, ll y) const {
        if (x > y) return 0;

        ll ans = 0;

        for (int i = r; i > 0; i -= i&-i) {
            ans += bit[i].index_right(y) - bit[i].index(x);
        }

        return ans;
    }

    // [l,r) 内の x以上の個数
    ll count_ge(int l, int r, ll x) const {
        return prefix_count_ge(r, x) - prefix_count_ge(l, x);
    }

    // [l,r) 内の x以下の個数
    ll count_le(int l, int r, ll x) const {
        return prefix_count_le(r, x) - prefix_count_le(l, x);
    }

    // [l,r) 内の x以上y以下の個数
    ll count_range(int l, int r, ll x, ll y) const {
        if (x > y) return 0;
        return prefix_count_range(r, x, y)
             - prefix_count_range(l, x, y);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    ll N; cin >> N;

    vector<tuple<ll,ll,ll>> query;
    vl IDX(1000000, -1);
    rep (i, N) {
        ll L, R; cin >> L >> R;
        query.push_back({L-1, 0, i});
        query.push_back({R-1, 1, i});
        IDX[L-1] = R;
    }
    sort(all(query));

    BITSortedMultiset B(1000000);
    ll ans = 0;
    for (auto [idx, a, qidx] : query) {
        if (a == 0) {
            ans += B.count_le(IDX[idx], 1000000, qidx);
            B.insert(IDX[idx], qidx);
        } else {
            B.remove(idx, qidx);
        }
    }

    print(ans);
}