#894475 (C++17) No.1282 Display Elements

• 問題: No.1282 Display Elements
• ユーザー: cutmdo
• 提出日時: 2023-07-22 05:29:56
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 186 ms / 2,000 ms
• コード長: 5,279 bytes
• コンパイル時間: 1,232 ms
• コンパイル使用メモリ: 105,100 KB
• 実行使用メモリ: 22,816 KB
• 最終ジャッジ日時: 2023-10-22 04:42:56
• 合計ジャッジ時間: 3,063 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	1 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	1 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	3 ms; 4,348 KB
testcase_11	AC	3 ms; 4,348 KB
testcase_12	AC	1 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	3 ms; 4,348 KB
testcase_15	AC	158 ms; 21,776 KB
testcase_16	AC	58 ms; 10,668 KB
testcase_17	AC	125 ms; 18,252 KB
testcase_18	AC	77 ms; 12,564 KB
testcase_19	AC	89 ms; 9,504 KB
testcase_20	AC	81 ms; 9,504 KB
testcase_21	AC	182 ms; 22,816 KB
testcase_22	AC	93 ms; 9,504 KB
testcase_23	AC	186 ms; 22,816 KB

ソースコード

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

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

class CoordinateCompression {

    const std::vector<long long> m_v;
    const std::vector<long long> m_itox;
    const std::unordered_map<long long, int> m_xtoi;

    static inline auto c_itox(const std::vector<long long>& v) {
        auto itox = v;
        std::sort(itox.begin(), itox.end());
        itox.erase(std::unique(itox.begin(), itox.end()), itox.end());
        return itox;
    }
    static inline auto c_xtoi(const std::vector<long long>& itox) {
        std::unordered_map<long long, int> xtoi;
        for(unsigned int i = 0; i < itox.size(); ++i) {
            xtoi.emplace(itox[i], i);
        }
        return xtoi;
    }

public:
    CoordinateCompression(const std::vector<long long>& v) :
        m_v(v),
        m_itox(c_itox(v)),
        m_xtoi(c_xtoi(m_itox)) {
    }
    auto size()const { return m_itox.size(); }
    auto toi(long long x)const { return m_xtoi.at(x); }
    auto tox(int i)const { return m_itox[i]; }
    auto c(const std::vector<long long>& v)const {
        std::vector<long long> ret; ret.reserve(size());
        for(const auto& x : v) { ret.emplace_back(toi(x)); }
        return ret;
    }
    auto c()const { return c(m_v); }
};

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, std::enable_if_t<isMonoid<Monoid>::value, std::nullptr_t> = nullptr >
class SegmentTree {
private:
    const int m_size;
    std::vector<Monoid> m_node;
    using S = decltype(Monoid().m_val);

    int calcSize(int n) const { int size = 1; while(size < n) { size <<= 1; }return size; }

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

    auto _query(int _l, int _r) const {
        _l = std::max(_l, 0); _r = std::min(_r, m_size - 1);
        auto l = _l + m_size;
        int r = _r + m_size;
        auto lm = Monoid();
        auto rm = Monoid();
        while(l <= r) {
            if(l & 1) { lm = lm.binaryOperation(m_node[l - 1]); ++l; }
            if(!(r & 1)) { rm = m_node[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 + m_size - 1] = Monoid(vec[i]);
        }
        for(int i = m_size - 2; i >= 0; --i) {
            m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
        }
    }
public:
    SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {}
    SegmentTree(int n, const std::vector<S>& vec) :SegmentTree(n) { _construct(vec); }

    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; }

    auto output()const {
        for(int i = 0; i < m_size; ++i) { std::cout << m_node[m_size + i - 1] << " "; }
        std::cout << std::endl;
    }
};


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());

    auto ab = a;
    for(const auto& x : b) { ab.emplace_back(x); }
    auto cc = CoordinateCompression(ab);

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

    cout << ans << endl;
}