結果
問題 | No.2859 Falling Balls |
ユーザー |
|
提出日時 | 2024-05-13 00:02:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,150 bytes |
コンパイル時間 | 2,576 ms |
コンパイル使用メモリ | 214,236 KB |
最終ジャッジ日時 | 2025-02-21 13:51:20 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 WA * 4 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename X>struct SegTree{using FX = function<X(X, X)>; // X•X -> X となる関数の型int n;FX fx;const X ex;vector<X> dat;SegTree(int n_, const FX &fx_, const X &ex_) : n(), fx(fx_), ex(ex_){int x = 1;while(n_ > x){x *= 2;}n = x;dat.assign(n * 2, ex);}X get(int i) const {return dat[i + n];}void set(int i, const X &x){ dat[i + n] = x; }void build(){for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);}void update(int i, const X &x){i += n;dat[i] = x;while(i > 0){i >>= 1; // parentdat[i] = fx(dat[i * 2], dat[i * 2 + 1]);}}X query(int a, int b){X vl = ex;X vr = ex;int l = a + n;int r = b + n;while(l < r){if(l & 1) vl = fx(vl, dat[l++]);if(r & 1) vr = fx(dat[--r], vr);l >>= 1;r >>= 1;}return fx(vl, vr);}X operator [](int i) const {return dat[i + n];}};template <typename T>struct compress{vector<T> sorted;vector<int> compressed;compress(const vector<T> &vec){int n = vec.size();compressed.resize(n);for(T x : vec){sorted.emplace_back(x);}sort(sorted.begin(), sorted.end());sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());for(int i = 0; i < n; ++i){compressed[i] = lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();}}int get(const T &x) const{return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();}T inv(const int x) const{return sorted[x];}size_t size() const{return sorted.size();}vector<T> getCompressed() const{return compressed;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long k;cin >> n >> k;vector<long long> t(n), x(n), c(n);for(int i = 0; i < n; i++){cin >> t[i];}for(int i = 0; i < n; i++){cin >> x[i];}for(int i = 0; i < n; i++){cin >> c[i];}vector<long long> a(n), b(n);for(int i = 0; i < n; i++){a[i] = k * t[i] + x[i];b[i] = k * t[i] - x[i];}compress<long long> compa(a), compb(b);int sizea = compa.size(), sizeb = compb.size();SegTree<long long> seg(sizea, [](long long a, long long b){ return max(a, b); }, 0);vector<vector<pair<long long, long long>>> v(sizeb);for(int i = 0; i < n; i++){v[compb.get(b[i])].emplace_back(compa.get(a[i]), c[i]);}for(int i = 0; i < sizeb; i++){sort(v[i].begin(), v[i].end());}for(int i = 0; i < sizeb; i++){for(auto [a, c] : v[i]){long long val = seg.query(0, a + 1);seg.update(a, val + c);}}cout << seg.query(0, sizea) << "\n";}