#735337 (C++17) No.1826 Fruits Collecting

提出ソース

結果

問題	No.1826 Fruits Collecting
ユーザー	fuppy_kyopro
提出日時	2022-01-28 23:09:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	11,593 bytes
コンパイル時間	5,426 ms
コンパイル使用メモリ	271,832 KB
実行使用メモリ	499,968 KB
最終ジャッジ日時	2023-08-28 21:46:37
合計ジャッジ時間	12,885 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 9,080 KB
testcase_01	AC	12 ms 6,552 KB
testcase_02	AC	12 ms 6,452 KB
testcase_03	AC	18 ms 7,096 KB
testcase_04	AC	7 ms 4,792 KB
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

//*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/

#include <bits/stdc++.h>

// #include <atcoder/all>

using namespace std;
// using namespace atcoder;

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_VEC(v)                                        \
    cerr << #v << ":";                                      \
    for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \
        cerr << " " << v[iiiiiiii];                         \
    cerr << endl;
#define DEBUG_MAT(v)                                \
    cerr << #v << endl;                             \
    for (int iv = 0; iv < v.size(); iv++) {         \
        for (int jv = 0; jv < v[iv].size(); jv++) { \
            cerr << v[iv][jv] << " ";               \
        }                                           \
        cerr << endl;                               \
    }
typedef long long ll;
// #define int ll

#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
    return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(), c.end()
void YES(bool t = true) {
    cout << (t ? "YES" : "NO") << endl;
}
void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }
void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }
void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }
void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }
void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1};
struct Setup_io {
    Setup_io() {
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cout << fixed << setprecision(25);
    }
} setup_io;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

template <typename T>
class SegmentTree {
  public:
    using F = function<T(T &, T &)>;
    int n;
    vector<T> dat;
    T e; // �P�ʌ�
    F query_func;
    F update_func;

    SegmentTree(vector<T> a, F query_func, F update_func, T e) : n(a.size()), query_func(query_func), update_func(update_func), e(e) {
        if (n == 0) {
            a.push_back(e);
            n++;
        }
        dat.resize(4 * n);
        init(0, 0, n, a);
    }

    void init(int k, int l, int r, vector<T> &a) {
        if (r - l == 1) {
            dat[k] = a[l];
        } else {
            int lch = 2 * k + 1, rch = 2 * k + 2;
            init(lch, l, (l + r) / 2, a);
            init(rch, (l + r) / 2, r, a);
            dat[k] = query_func(dat[lch], dat[rch]);
        }
    }

    //k�Ԗڂ̒l��a�ɕύX
    void update(int k, T a, int v, int l, int r) {
        if (r - l == 1) {
            dat[v] = update_func(dat[v], a);
        } else {
            if (k < (l + r) / 2)
                update(k, a, 2 * v + 1, l, (l + r) / 2);
            else {
                update(k, a, 2 * v + 2, (l + r) / 2, r);
            }
            dat[v] = query_func(dat[v * 2 + 1], dat[v * 2 + 2]);
        }
    }

    //[a,b)�̍ŏ��l�����߂�
    //���̂ق��̈����͌v�Z�̊ȒP�̂��߂̈���
    //k�͐ړ_�̔ԍ�,l,r�͂��̐ړ_��[l,r)�ɑΉ����Ă��邱�Ƃ�\��
    //�]���āA�O�����query(a,b,0,0,n)�Ƃ��Ă��
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return e;
        }
        if (a <= l && r <= b) {
            return dat[k];
        } else {
            T ul = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T ur = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return query_func(ul, ur);
        }
    }

    // �����𖞂����ĉE��T��
    int find(int a, int b, int k, int l, int r, int x) {
        // �����𒼂�
        if (dat[k] < x || r <= a || b <= l) return -1;
        if (l + 1 == r) {
            // �����𒼂�
            if (dat[k] >= x)
                return l;
            else
                return -1;
        }
        int rv = find(a, b, 2 * k + 2, (l + r) / 2, r, x);
        if (rv != -1) return rv;
        return find(a, b, 2 * k + 1, l, (l + r) / 2, x);
    }
};

ll fff(ll a, ll b) { return max(a, b); }
ll ggg(ll a, ll b) { return max(a, b); }

template <typename structure_t, typename get_t, typename update_t>
struct SegmentTree2DCompressed {

    using merge_f = function<get_t(get_t, get_t)>;
    using range_get_f = function<get_t(structure_t &, int, int)>;
    using update_f = function<void(structure_t &, int, update_t)>;

    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);
        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(structure_t(vl(beet[k].size(), -INF), fff, ggg, -INF));
        }
    }

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

ll ff(ll a, ll b) { return max(a, b); }
ll gg(SegmentTree<ll> &seg, int a, int b) { return seg.query(a, b, 0, 0, seg.n); }
void hh(SegmentTree<ll> &seg, int a, ll b) { seg.update(a, b, 0, 0, seg.n); }

template <typename T>
class Zaatsu {
    bool is_build;
    vector<T> elements;

  public:
    Zaatsu() : is_build(false) {}

    void add(T x) {
        elements.push_back(x);
    }

    void add(vector<T> x) {
        for (int i = 0; i < (int)x.size(); i++) {
            elements.push_back(x[i]);
        }
    }

    int build() {
        sort(elements.begin(), elements.end());
        UNIQUE(elements);
        is_build = true;
        return elements.size();
    }

    int operator[](T x) {
        assert(is_build);
        return lower_bound(elements.begin(), elements.end(), x) - elements.begin();
    }

    T original(int i) {
        assert(is_build);
        return elements[i];
    }
};

signed main() {
    int n;
    cin >> n;

    using tup = tuple<ll, ll, ll>;
    vector<tup> txv(n);
    rep(i, n) {
        int t, x, v;
        cin >> t >> x >> v;
        txv[i] = tup(t, x, v);
    }
    sort(all(txv));

    Zaatsu<ll> zax, zatx1, zatx2;
    zax.add(0);
    zatx1.add(0);
    zatx2.add(0);
    rep(i, n) {
        auto [t, x, v] = txv[i];
        zax.add(x);
        zatx1.add(t - x);
        zatx2.add(t + x);
    }
    zax.build();
    zatx1.build();
    zatx2.build();

    SegmentTree2DCompressed<SegmentTree<ll>, ll, ll> dp1(n + 1, ff, gg, hh, -INF), dp2(n + 1, ff, gg, hh, -INF);

    rep(i, n) {
        auto [t, x, v] = txv[i];

        int xi = zax[x];
        int tx1i = zatx1[t - x];
        int tx2i = zatx2[t + x];
        dp1.preupdate(tx1i, xi);
        dp2.preupdate(tx2i, xi);
    }
    int xi = zax[0];
    int tx1i = zatx1[0];
    int tx2i = zatx2[0];
    dp1.preupdate(tx1i, xi);
    dp2.preupdate(tx2i, xi);

    dp1.build();
    dp2.build();

    dp1.update(tx1i, xi, 0);
    dp2.update(tx2i, xi, 0);

    ll ans = 0;
    rep(i, n) {
        auto [t, x, v] = txv[i];

        int xi = zax[x];
        int tx1i = zatx1[t - x];
        int tx2i = zatx2[t + x];

        ll ma1 = dp1.query(0, tx1i + 1, 0, xi + 1);
        ll ma2 = dp2.query(0, tx2i + 1, xi, n + 1);

        ll ma = max(ma1, ma2) + v;
        chmax(ans, ma);
        dp1.update(tx1i, xi, ma);
        dp2.update(tx2i, xi, ma);
    }

    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード