結果

問題 No.1826 Fruits Collecting
ユーザー ei1333333ei1333333
提出日時 2022-01-28 23:03:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 8,728 bytes
コンパイル時間 5,537 ms
コンパイル使用メモリ 291,940 KB
実行使用メモリ 208,440 KB
最終ジャッジ日時 2023-08-28 21:41:35
合計ジャッジ時間 42,488 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,376 KB
testcase_01 AC 5 ms
4,648 KB
testcase_02 AC 5 ms
4,660 KB
testcase_03 AC 8 ms
4,892 KB
testcase_04 AC 4 ms
4,380 KB
testcase_05 AC 719 ms
91,584 KB
testcase_06 AC 1,375 ms
170,688 KB
testcase_07 AC 819 ms
99,132 KB
testcase_08 AC 52 ms
13,472 KB
testcase_09 AC 1,170 ms
119,980 KB
testcase_10 AC 765 ms
96,292 KB
testcase_11 AC 717 ms
94,896 KB
testcase_12 AC 241 ms
43,988 KB
testcase_13 AC 103 ms
22,856 KB
testcase_14 AC 169 ms
28,208 KB
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 AC 1,977 ms
207,168 KB
testcase_23 TLE -
testcase_24 TLE -
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 283 ms
48,664 KB
testcase_31 AC 650 ms
95,260 KB
testcase_32 AC 335 ms
47,364 KB
testcase_33 AC 1,556 ms
171,396 KB
testcase_34 AC 1,161 ms
111,752 KB
testcase_35 AC 193 ms
28,432 KB
testcase_36 AC 1,559 ms
171,196 KB
testcase_37 AC 85 ms
11,036 KB
testcase_38 AC 59 ms
8,644 KB
testcase_39 AC 759 ms
109,884 KB
testcase_40 AC 976 ms
172,080 KB
testcase_41 AC 183 ms
41,196 KB
testcase_42 AC 21 ms
7,856 KB
testcase_43 AC 1 ms
4,376 KB
testcase_44 AC 1 ms
4,376 KB
testcase_45 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;

using int64 = long long;
// const int mod = 1e9 + 7;
const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in: v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e: t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


/**
 * @brief Binary-Indexed-Tree(BIT)
 * @docs docs/binary-indexed-tree.md
 */
struct BinaryIndexedTree {
private:
  vector< int64 > data;

public:
  explicit BinaryIndexedTree(size_t sz) : data(sz + 1, -infll) {}

  void add(int k, const int64 &x) {
    for(++k; k < (int) data.size(); k += k & -k) data[k] = max(data[k], x);
  }

  int64 fold(int r) const {
    int64 ret = -infll;
    for(; r > 0; r -= r & -r) ret = max(ret, data[r]);
    return ret;
  }
};

template< typename structure_t, typename get_t, typename update_t, typename merge_f, typename range_get_f, typename update_f >
struct SegmentTree2DCompressed {

  int sz;
  vector< structure_t > seg;
  const merge_f f;
  const range_get_f g;
  const update_f h;
  const get_t identity;
  vector< vector< int > > LL, RR;
  vector< vector< int > > beet;

  SegmentTree2DCompressed(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity)
      : f(f), g(g), h(h), identity(identity) {
    sz = 1;
    while(sz < n) sz <<= 1;
    beet.resize(2 * sz);
    LL.resize(2 * sz);
    RR.resize(2 * sz);
  }

  void update(int a, int x, update_t z, int k, int l, int r) {
    if(r <= a || a + 1 <= l) return;
    if(a <= l && r <= a + 1) return h(seg[k], x, z);
    update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1);
    update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r);
    return h(seg[k], x, z);
  }

  void update(int x, int y, update_t z) {
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return update(x, y, z, 1, 0, sz);
  }

  get_t query(int a, int b, int y, int k, int l, int r) {
    if(a >= r || b <= l) return identity;
    if(a <= l && r <= b) return g(seg[k], y);
    return f(query(a, b, LL[k][y], 2 * k + 0, l, (l + r) >> 1),
             query(a, b, RR[k][y], 2 * k + 1, (l + r) >> 1, r));
  }

  get_t query(int a, int b, int y) {
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return query(a, b, y, 1, 0, sz);
  }

  void build() {
    for(int k = (int) beet.size() - 1; k >= sz; k--) {
      sort(begin(beet[k]), end(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
    }
    for(int k = sz - 1; k > 0; k--) {
      beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size());
      merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]), begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
      LL[k].resize(beet[k].size() + 1);
      RR[k].resize(beet[k].size() + 1);
      int tail1 = 0, tail2 = 0;
      for(int i = 0; i < beet[k].size(); i++) {
        while(tail1 < beet[2 * k + 0].size() && beet[2 * k + 0][tail1] < beet[k][i]) ++tail1;
        while(tail2 < beet[2 * k + 1].size() && beet[2 * k + 1][tail2] < beet[k][i]) ++tail2;
        LL[k][i] = tail1, RR[k][i] = tail2;
      }
      LL[k][beet[k].size()] = (int) beet[2 * k + 0].size();
      RR[k][beet[k].size()] = (int) beet[2 * k + 1].size();
    }
    for(int k = 0; k < beet.size(); k++) {
      seg.emplace_back(beet[k].size());
    }
  }

  void preupdate(int x, int y) {
    beet[x + sz].push_back(y);
  }
};


template< typename structure_t, typename get_t, typename update_t, typename merge_f, typename range_get_f, typename update_f >
struct SegmentTree2DCompressed2 {

  int sz;
  vector< structure_t > seg;
  const merge_f f;
  const range_get_f g;
  const update_f h;
  const get_t identity;
  vector< vector< int > > beet;

  SegmentTree2DCompressed2(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity)
      : f(f), g(g), h(h), identity(identity) {
    beet.resize(n + 1);
  }

  void update(int k, int y, update_t z) {
    for(++k; k < (int) beet.size(); k += k & -k) {
      auto y2 = lower_bound(begin(beet[k]), end(beet[k]), y) - begin(beet[k]);
      h(seg[k], y2, z);
    }
  }

  get_t query(int k, int y) {
    get_t ret = identity;
    for(; k > 0; k -= k & -k) {
      auto y2 = lower_bound(begin(beet[k]), end(beet[k]), y) - begin(beet[k]);

      ret = f(ret, g(seg[k], y2));
    }
    return ret;
  }

  void build() {
    for(int k = 0; k < (int) beet.size(); k++) {
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
      seg.emplace_back(beet[k].size());
    }
  }

  void preupdate(int k, int y) {
    for(++k; k < (int) beet.size(); k += k & -k) {
      beet[k].emplace_back(y);
    }
  }
};

int main() {
  int N;
  cin >> N;
  vector< tuple< int, int, int > > ds;
  ds.reserve(N + 1);
  for(int i = 0; i < N; i++) {
    int t, x, v;
    cin >> t >> x >> v;
    ds.emplace_back(t, x, v);
  }
  ds.emplace_back(0, 0, 0);
  sort(begin(ds), end(ds));
  vector< int64 > dp(ds.size(), -infll);
  dp[0] = 0;
  vector< int > l, r, m;
  l.reserve(N + 1);
  r.reserve(N + 1);
  m.reserve(N + 1);
  for(auto&[t, x, v]: ds) {
    l.emplace_back(t + x);
    r.emplace_back(t - x);
    m.emplace_back(x);
  }
  sort(begin(l), end(l));
  l.erase(unique(begin(l), end(l)), end(l));
  sort(begin(r), end(r));
  r.erase(unique(begin(r), end(r)), end(r));
  sort(begin(m), end(m));
  m.erase(unique(begin(m), end(m)), end(m));
  vector< int > ldx(ds.size()), rdx(ds.size()), mdx(ds.size());
  for(int i = 0; i < (int) ds.size(); i++) {
    auto[t, x, v]=ds[i];
    ldx[i] = lower_bound(begin(l), end(l), t + x) - begin(l);
    rdx[i] = lower_bound(begin(r), end(r), t - x) - begin(r);
    mdx[i] = lower_bound(begin(m), end(m), x) - begin(m);
  }
  auto f = [](int64 a, int64 b) { return max(a, b); };
  // みんなの2D segment tree
  using BIT = BinaryIndexedTree;
  auto g = [](BIT &k, int y) { return k.fold(y); };
  auto h = [](BIT &k, int x, int64 y) { k.add(x, y); };

  SegmentTree2DCompressed< BIT, int64, int64, decltype(f), decltype(g), decltype(h) > lseg(m.size(), f, g, h, -infll);
  SegmentTree2DCompressed2< BIT, int64, int64, decltype(f), decltype(g), decltype(h) > rseg(m.size(), f, g, h, -infll);
  vector< int > ord(ds.size());
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), [&](int a, int b) { return rdx[a] < rdx[b]; });
  for(int i: ord) rseg.preupdate(mdx[i], rdx[i]);
  for(int i = 0; i < (int) ds.size(); i++) {
    lseg.preupdate(mdx[i], ldx[i]);
  }
  lseg.build();
  rseg.build();
  lseg.update(mdx[0], ldx[0], 0);
  rseg.update(mdx[0], rdx[0], 0);
  int64 ret = 0;
  for(int i = 1; i < (int) ds.size(); i++) {
    auto[t2, x2, v2] = ds[i];
    auto v = max(lseg.query(mdx[i], m.size(), ldx[i] + 1), rseg.query(mdx[i], rdx[i] + 1));
    v += v2;
    if(v >= 0) {
      chmax(ret, v);
      lseg.update(mdx[i], ldx[i], v);
      rseg.update(mdx[i], rdx[i], v);
    }
  }
  cout << ret << "\n";
}
0