結果
| 問題 | No.1826 Fruits Collecting |
| ユーザー |
 ei1333333
|
| 提出日時 | 2022-01-29 00:56:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,433 bytes |
| コンパイル時間 | 2,979 ms |
| コンパイル使用メモリ | 227,560 KB |
| 最終ジャッジ日時 | 2025-01-27 17:37:00 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 WA * 3 TLE * 10 |
ソースコード
#include <bits/stdc++.h>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)};}#line 1 "structure/wavelet/succinct-indexable-dictionary.cpp"/*** @brief Succinct Indexable Dictionary(完備辞書)*/struct SuccinctIndexableDictionary {size_t length;size_t blocks;vector< unsigned > bit, sum;SuccinctIndexableDictionary() = default;SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {bit.assign(blocks, 0U);sum.assign(blocks, 0U);}void set(int k) {bit[k >> 5] |= 1U << (k & 31);}void build() {sum[0] = 0U;for(int i = 1; i < blocks; i++) {sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);}}bool operator[](int k) {return (bool((bit[k >> 5] >> (k & 31)) & 1));}int rank(int k) {return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));}int rank(bool val, int k) {return (val ? rank(k) : k - rank(k));}};/*** @brief Segment Tree(セグメント木)* @docs docs/segment-tree.md*/template< typename Monoid >struct SegmentTree {int n, sz;vector< Monoid > seg;Monoid M1;SegmentTree() = default;SegmentTree(int n, const Monoid &M1) : n(n), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}SegmentTree(const vector< Monoid > &v, const Monoid &M1) :SegmentTree((int) v.size(), M1) {build(v);}void build(const vector< Monoid > &v) {assert(n == (int) v.size());for(int k = 0; k < n; k++) seg[k + sz] = v[k];for(int k = sz - 1; k > 0; k--) {seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]); // 書き方が分かりません...}}void set(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1) {seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid get(int k) const {return seg[k + sz];}Monoid operator[](const int &k) const {return get(k);}void apply(int k, const Monoid &x) {k += sz;seg[k] = max(seg[k], x);while(k >>= 1) {seg[k] = max(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid prod(int l, int r) const {Monoid L = M1, R = M1;for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) {if(l & 1) L = max(L, seg[l++]);if(r & 1) R = max(seg[--r], R);}return max(L, R);}Monoid all_prod() const {return seg[1];}};#line 3 "structure/wavelet/wavelet-matrix-point-add-rectangle-sum.cpp"/** @brief Wavelet Matrix Point Add Rectangle Sum* @docs docs/wavelet-matrix-point-add-rectangle-sum.md*/template< typename T, int MAXLOG, typename D >struct WaveletMatrixPointApplyRectangleProd {size_t length;SuccinctIndexableDictionary matrix[MAXLOG];SegmentTree< D > ds[MAXLOG];vector< T > v;const D d0;int mid[MAXLOG];WaveletMatrixPointApplyRectangleProd() = default;WaveletMatrixPointApplyRectangleProd(const vector< T > &v, const vector< D > &d, const D &d0): length(v.size()), v(v), d0(d0) {assert(v.size() == d.size());vector< int > l(length), r(length), ord(length);iota(begin(ord), end(ord), 0);vector< D > dd(length);for(int level = MAXLOG - 1; level >= 0; level--) {matrix[level] = SuccinctIndexableDictionary(length + 1);int left = 0, right = 0;for(int i = 0; i < length; i++) {if(((v[ord[i]] >> level) & 1)) {matrix[level].set(i);r[right++] = ord[i];} else {l[left++] = ord[i];}}mid[level] = left;matrix[level].build();ord.swap(l);for(int i = 0; i < right; i++) {ord[left + i] = r[i];}for(int i = 0; i < length; i++) {dd[i] = d[ord[i]];}ds[level] = SegmentTree< D >(length, d0);}}pair< int, int > succ(bool f, int l, int r, int level) {return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};}// count d[i] s.t. (l <= i < r) && (v[i] < upper)D rect_max(int l, int r, T upper) {D ret = d0;for(int level = MAXLOG - 1; level >= 0; level--) {if(((upper >> level) & 1)) {auto nxt = succ(false, l, r, level);ret = max(ret, ds[level].prod(nxt.first, nxt.second));l = l - nxt.first + mid[level];r = r - nxt.second + mid[level];} else {tie(l, r) = succ(false, l, r, level);}}return ret;}void point_add(int k, const D &x) {auto &y = v[k];for(int level = MAXLOG - 1; level >= 0; level--) {bool f = ((y >> level) & 1);k = matrix[level].rank(f, k) + mid[level] * f;ds[level].apply(k, x);}}};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;vector< pair< int, int > > m;l.reserve(N + 1);r.reserve(N + 1);m.reserve(N + 1);for(int i = 0; i < (int) ds.size(); i++) {auto[t, x, v]=ds[i];l.emplace_back(t + x);r.emplace_back(t - x);m.emplace_back(x, i);}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));vector< int > ldx(ds.size()), rdx(ds.size()), mdx(ds.size());vector< int > ldh(ds.size()), rdh(ds.size());vector< int64 > dv(ds.size(), -infll);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), make_pair(x, i)) - begin(m);ldh[mdx[i]] = ldx[i];rdh[mdx[i]] = rdx[i];}WaveletMatrixPointApplyRectangleProd< int, 17, int64 > lseg(ldh, dv, -infll);WaveletMatrixPointApplyRectangleProd< int, 17, int64 > rseg(rdh, dv, -infll);lseg.point_add(mdx[0], 0);rseg.point_add(mdx[0], 0);int64 ret = 0;for(int i = 1; i < (int) ds.size(); i++) {auto[t2, x2, v2] = ds[i];auto v = max(lseg.rect_max(mdx[i], m.size(), ldx[i] + 1), rseg.rect_max(0, mdx[i], rdx[i] + 1));v += v2;chmax(ret, v);lseg.point_add(mdx[i], v);rseg.point_add(mdx[i], v);}cout << ret << "\n";}