Submission #6845174


Source Code Expand

Copy
#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

Submission Time
Task D - Summer Vacation
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2692 Byte
Status
Exec Time 96 ms
Memory 3968 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB
testcase_01 16 ms 1536 KB
testcase_02 6 ms 1280 KB
testcase_03 56 ms 2048 KB
testcase_04 95 ms 3840 KB
testcase_05 96 ms 3840 KB
testcase_06 65 ms 2816 KB
testcase_07 95 ms 3840 KB
testcase_08 23 ms 1280 KB
testcase_09 51 ms 3328 KB
testcase_10 77 ms 3840 KB
testcase_11 74 ms 3712 KB
testcase_12 21 ms 1152 KB
testcase_13 82 ms 3840 KB
testcase_14 72 ms 3712 KB
testcase_15 6 ms 512 KB
testcase_16 80 ms 3968 KB
testcase_17 12 ms 768 KB
testcase_18 78 ms 3840 KB