結果

問題 No.1282 Display Elements
ユーザー cutmdocutmdo
提出日時 2023-07-22 05:27:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,288 ms / 2,000 ms
コード長 3,679 bytes
コンパイル時間 1,049 ms
コンパイル使用メモリ 100,504 KB
実行使用メモリ 61,080 KB
最終ジャッジ日時 2024-09-22 05:59:58
合計ジャッジ時間 9,390 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 4 ms
6,944 KB
testcase_11 AC 4 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 5 ms
6,944 KB
testcase_14 AC 7 ms
6,940 KB
testcase_15 AC 1,180 ms
57,620 KB
testcase_16 AC 389 ms
27,696 KB
testcase_17 AC 967 ms
51,104 KB
testcase_18 AC 585 ms
43,176 KB
testcase_19 AC 315 ms
6,944 KB
testcase_20 AC 332 ms
6,940 KB
testcase_21 AC 1,255 ms
61,080 KB
testcase_22 AC 379 ms
6,944 KB
testcase_23 AC 1,288 ms
61,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/1282"

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <utility>
#include <unordered_map>

template<class T>
class isMonoid {
    template <class U>
    static auto check(U x) -> decltype(x.binaryOperation(x), std::true_type{});
    static std::false_type check(...);
public:
    static bool const value = decltype(check(std::declval<T>()))::value;
};

template<class Monoid, int size = static_cast<int>(1e9 + 1), std::enable_if_t<isMonoid<Monoid>::value, std::nullptr_t> = nullptr>
class DynamicSegmentTree {
private:
    std::unordered_map<int, Monoid> m_node;
    using S = decltype(Monoid().m_val);

    auto _get(int i)const { return (m_node.find(i) == m_node.end()) ? Monoid() : m_node.at(i); }

    template<class Lambda>
    auto _update_op(int itr, Monoid&& val, const Lambda& op) {
        int i = itr + size - 1;
        m_node[i] = op(_get(i), std::forward<decltype(val)>(val));
        while(i) {
            i = (i - 1) >> 1;
            m_node[i] = _get((i << 1) | 1).binaryOperation(_get((i + 1) << 1LL));
        }
    }

    auto _query(int _l, int _r) const {
        _l = std::max(_l, 0); _r = std::min(_r, size - 1);
        auto l = _l + size;
        int r = _r + size;
        auto lm = Monoid();
        auto rm = Monoid();
        while(l <= r) {
            if(l & 1) { lm = lm.binaryOperation(_get(l - 1)); ++l; }
            if(!(r & 1)) { rm = _get(r - 1).binaryOperation(rm); --r; }
            l >>= 1, r >>= 1;
        }
        return lm.binaryOperation(rm);
    }

    auto _construct(const std::vector<S>& vec) {
        for(unsigned int i = 0; i < vec.size(); ++i) {
            m_node[i + size - 1] = Monoid(vec[i]);
        }
        for(int i = size - 2; i >= 0; --i) {
            m_node[i] = _get((i << 1) | 1).binaryOperation(_get((i + 1) << 1));
        }
    }
public:
    DynamicSegmentTree() {}

    template<class Lambda>
    auto update_op(int itr, Monoid&& val, const Lambda& op) { return _update_op(itr, std::forward<Monoid>(val), op); }
    auto update(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid&, const Monoid& m2) {return m2; }); }
    auto add(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid& m1, const Monoid& m2) {return Monoid(m1.m_val + m2.m_val); }); }
    auto query(int l, int r)const { return _query(l, r).m_val; }
    auto query_all()const { return m_node[0].m_val; }
};


template<
    class S,   // 要素の型
    S element, // 元
    class T // lambdaはC++20じゃないと渡せなかった．．．
    // S T(S, S)  // 2項演算子
>
struct Monoid {
    S m_val;
    Monoid() :m_val(element) {}
    Monoid(S val) :m_val(val) {}
    Monoid binaryOperation(const Monoid& m2)const { return T()(m_val, m2.m_val); }
    friend std::ostream& operator<<(std::ostream& os, const Monoid<S, element, T>& m) {
        return os << m.m_val;
    }
};


using ll = long long;
using std::cout;
using std::cin;
constexpr char endl = '\n';

struct Functor { auto operator()(ll a, ll b)const { return a + b; } };
using M = Monoid<ll, 0, Functor>;

signed main() {
    ll n;
    cin >> n;
    std::vector<ll> a, b;
    a.reserve(n); b.reserve(n);
    for(int i = 0; i < n; ++i) {
        ll x; cin >> x; a.emplace_back(x);
    }
    for(int i = 0; i < n; ++i) {
        ll x; cin >> x; b.emplace_back(x);
    }
    std::sort(a.begin(), a.end());

    ll ans = 0;
    auto segtree = DynamicSegmentTree<M>();
    for(int i = 0; i < n; ++i) {
        segtree.add(b[i], 1);
        ans += segtree.query(0, a[i] - 1);
    }

    cout << ans << endl;
}
0