結果
| 問題 | No.1826 Fruits Collecting |
| ユーザー |
 ei1333333
|
| 提出日時 | 2022-01-28 22:30:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,389 bytes |
| コンパイル時間 | 5,300 ms |
| コンパイル使用メモリ | 279,804 KB |
| 最終ジャッジ日時 | 2025-01-27 16:57:08 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 TLE * 14 |
ソースコード
#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) chmax(data[k], x);}int64 fold(int r) const {int64 ret = -infll;for(; r > 0; r -= r & -r) chmax(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 x, int y, int k, int l, int r) {if(a >= r || b <= l) return identity;if(a <= l && r <= b) return g(seg[k], x, y);return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1),query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r));}get_t query(int a, int b, int x, int y) {x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]);y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);return query(a, b, x, 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);}};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 treeusing BIT = BinaryIndexedTree;auto g = [](BIT &k, int x, 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);SegmentTree2DCompressed< BIT, int64, int64, decltype(f), decltype(g), decltype(h) > rseg(m.size(), f, g, h, -infll);for(int i = 0; i < (int) ds.size(); i++) {lseg.preupdate(mdx[i], ldx[i]);rseg.preupdate(mdx[i], rdx[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(), 0, ldx[i] + 1), rseg.query(0, mdx[i], 0, rdx[i] + 1));v += v2;chmax(ret, v);lseg.update(mdx[i], ldx[i], v);rseg.update(mdx[i], rdx[i], v);}cout << ret << "\n";}