結果

問題 No.2859 Falling Balls
ユーザー shobonvipshobonvip
提出日時 2024-08-25 16:15:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 983 ms / 3,000 ms
コード長 5,431 bytes
コンパイル時間 6,484 ms
コンパイル使用メモリ 336,136 KB
実行使用メモリ 175,872 KB
最終ジャッジ日時 2024-08-25 16:15:37
合計ジャッジ時間 21,459 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

//https://hitonanode.github.io/cplib-cpp/segmenttree/rangetree.hpp.html

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// 逆元を要求しない領域木
template <class S, S (*op)(S, S), S (*e)(), class Coordinate> class rangetree {
    int n;
    using Pt = std::pair<Coordinate, Coordinate>;
    std::vector<Pt> _pts;
    std::vector<std::vector<Pt>> _range2yxs;
    std::vector<atcoder::segtree<S, op, e>> segtrees;
    void _set(int v, Pt p, S val) {
        auto i = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));
        segtrees[v].set(i, val);
    }
    void _add(int v, Pt p, S val) {
        auto i = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));
        segtrees[v].set(i, op(segtrees[v].get(i), val));
    }
    S _prod(int v, Coordinate yl, Coordinate yr) const {
        auto comp = [&](const Pt &l, const Pt &r) { return l.first < r.first; };
        auto il = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yl, yl}, comp));
        auto ir = std::distance(
            _range2yxs[v].begin(),
            std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yr, yr}, comp));
        return segtrees[v].prod(il, ir);
    }

public:
    rangetree() = default;
    void add_point(Coordinate x, Coordinate y) noexcept { _pts.emplace_back(x, y); }
    void build() {
        std::sort(_pts.begin(), _pts.end());
        _pts.erase(std::unique(_pts.begin(), _pts.end()), _pts.end());
        n = _pts.size();

        _range2yxs.resize(n * 2);
        for (int i = 0; i < n; i++) _range2yxs[n + i] = {{_pts[i].second, _pts[i].first}};
        for (int i = n - 1; i > 0; i--) {
            auto &lch = _range2yxs[i * 2];
            auto &rch = _range2yxs[i * 2 + 1];
            std::merge(
                lch.begin(), lch.end(), rch.begin(), rch.end(), std::back_inserter(_range2yxs[i]));
            _range2yxs[i].erase(
                std::unique(_range2yxs[i].begin(), _range2yxs[i].end()), _range2yxs[i].end());
        }
        for (const auto &v : _range2yxs) segtrees.emplace_back(v.size());
    }
    void set(Coordinate x, Coordinate y, S val) {
        int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));
        assert(i < n and _pts[i] == std::make_pair(x, y));
        for (i += n; i; i >>= 1) _set(i, {x, y}, val);
    }
    void add(Coordinate x, Coordinate y, S val) {
        int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));
        assert(i < n and _pts[i] == std::make_pair(x, y));
        for (i += n; i; i >>= 1) _add(i, {x, y}, val);
    }
    S prod(Coordinate xl, Coordinate xr, Coordinate yl, Coordinate yr) const {
        auto comp = [](const Pt &l, const Pt &r) { return l.first < r.first; };
        int l = n + std::distance(_pts.begin(),
                                  std::lower_bound(_pts.begin(), _pts.end(), Pt{xl, yr}, comp));
        int r = n + std::distance(_pts.begin(),
                                  std::lower_bound(_pts.begin(), _pts.end(), Pt{xr, yr}, comp));
        S ret = e();
        while (l < r) {
            if (l & 1) ret = op(ret, _prod(l++, yl, yr));
            if (r & 1) ret = op(ret, _prod(--r, yl, yr));
            l >>= 1, r >>= 1;
        }
        return ret;
    }
    S get(Coordinate x, Coordinate y) const { return prod(x, x + 1, y, y + 1); }
};

ll op(ll a, ll b){
	return max(a, b);
}
ll e(){
	return -1e18;
}


int main(){
	int n; cin >> n;
	ll k; cin >> k;
	vector<ll> t(n), x(n), c(n);
	vector<tuple<ll,ll,ll>> f(n);
	rep(i,0,n) cin >> t[i];
	rep(i,0,n) cin >> x[i];
	rep(i,0,n) cin >> c[i];
	rep(i,0,n) f[i] = make_tuple(t[i], x[i], c[i]);
	sort(f.begin(), f.end());
	rep(i,0,n){
		t[i] = get<0>(f[i]);
		x[i] = get<1>(f[i]);
		c[i] = get<2>(f[i]);
	}
	
	rangetree<ll,op,e,ll> wm;
	rep(i,0,n){
		wm.add_point(x[i]+k*t[i], x[i]-k*t[i]);
	}
	wm.add_point(0, 0);

	wm.build();
	wm.set(0, 0, 0);
	
	rep(i,0,n){
		ll X = x[i]+k*t[i];
		ll Y = x[i]-k*t[i];
		ll Z = wm.prod(-9e18, X+1, Y, 9e18) + c[i];
		wm.set(X, Y, Z);
	}

	cout << wm.prod(-9e18, 9e18, -9e18, 9e18) << '\n';

}
0