Submission #6845174

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N,M;
vector<PLL> tasks;

template <typename T>
class SegTree {
 private:
    int _n;
    T _init_val;
    std::vector<T> _data;
    std::function<T(T, T)> _f;

    T _query(int a, int b, int k, int l, int r) {
        // [a b)と[l r]が交差しない
        if (r <= a || b <= l) return _init_val;

        // [a b)が[l r]を含む
        if (a <= l && r <= b) return _data[k];

        T vl = _query(a, b, k*2+1, l, (l+r)/2);
        T vr = _query(a, b, k*2+2, (l+r)/2, r);

        return _f(vl, vr);
    }

 public:
    SegTree(int n, T init_val, std::function<T(T, T)> f) {
        _init_val = init_val;
        _n = 1;
        _f = f;

        while (_n < n)
            _n *= 2;
        _data.resize(2 * _n, init_val);
    }

    T get(int k) {
        return _data[k + _n - 1];
    }

    void update(int k, T a) {
        k += _n-1;
        _data[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            _data[k] = _f(_data[k*2+1], _data[k*2+2]);
        }
    }

    // [a b)の範囲でfを適用
    T query(int a, int b) {
        return _query(a, b, 0, 0, _n);
    }

    // 先頭からチェックし，はじめてxを満たしたインデックス
    int lower_bound(T x) {
        return _lower_bound(x, 0);
    }

    int _lower_bound(T x, int k) {
        if (k >= _n-1) {
            return k - (_n - 1);  // 葉
        } else if (_data[k] < x) {
            return _n;  // 該当なし
        } else if (x <= _data[k * 2 + 1]) {
            return _lower_bound(x, k * 2 + 1);
        } else {
            return _lower_bound(x - _data[k * 2 + 1] , k * 2 + 2);
        }
    }
};

signed main() {
  cin>>N>>M;
  tasks.resize(N);
  // used.resize(M+1, false);

  SegTree<ll> st(M+1, -1, [](const ll &x, const ll &y) { return max(x,y); });
  rep(i,M+1)
    st.update(i,i);

  rep(i,N)
    cin>>tasks[i].first>>tasks[i].second;
  sort(begin(tasks), end(tasks), [](const PLL &l, const PLL &r) {
      if (l.second == r.second) {
        return r.first < l.first;
      }
      return l.second > r.second;
      });

  ll ans = 0;
  rep(i,N) {
    // ll pos = f(0, M-tasks[i].first);
    ll pos = st.query(0, M-tasks[i].first+1);
    if (pos != -1) {
      // printf("%d %d %d\n", tasks[i].first, tasks[i].second, pos);
      st.update(pos, -1);
      ans += tasks[i].second;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result