結果
問題 | No.2859 Falling Balls |
ユーザー | dyktr_06 |
提出日時 | 2024-07-15 14:12:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 571 ms / 3,000 ms |
コード長 | 3,540 bytes |
コンパイル時間 | 3,337 ms |
コンパイル使用メモリ | 229,264 KB |
実行使用メモリ | 43,344 KB |
最終ジャッジ日時 | 2024-07-15 14:12:27 |
合計ジャッジ時間 | 12,933 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 117 ms
14,180 KB |
testcase_11 | AC | 438 ms
39,568 KB |
testcase_12 | AC | 17 ms
6,940 KB |
testcase_13 | AC | 399 ms
37,432 KB |
testcase_14 | AC | 339 ms
33,328 KB |
testcase_15 | AC | 108 ms
13,952 KB |
testcase_16 | AC | 149 ms
18,340 KB |
testcase_17 | AC | 143 ms
17,948 KB |
testcase_18 | AC | 12 ms
6,944 KB |
testcase_19 | AC | 258 ms
24,216 KB |
testcase_20 | AC | 532 ms
43,292 KB |
testcase_21 | AC | 511 ms
43,264 KB |
testcase_22 | AC | 512 ms
43,264 KB |
testcase_23 | AC | 571 ms
43,248 KB |
testcase_24 | AC | 542 ms
43,264 KB |
testcase_25 | AC | 547 ms
43,320 KB |
testcase_26 | AC | 533 ms
43,248 KB |
testcase_27 | AC | 535 ms
43,228 KB |
testcase_28 | AC | 558 ms
43,244 KB |
testcase_29 | AC | 506 ms
43,344 KB |
ソースコード
#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; // parent dat[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; assert(n >= 1 && n <= 200000); assert(k >= 1 && k <= 1000000000LL); vector<long long> t(n), x(n), c(n); for(int i = 0; i < n; i++){ cin >> t[i]; assert(t[i] >= 1 && t[i] <= 1000000000LL); } for(int i = 0; i < n; i++){ cin >> x[i]; assert(abs(x[i]) <= 1000000000LL); } for(int i = 0; i < n; i++){ cin >> c[i]; assert(c[i] >= 1 && c[i] <= 1000000000LL); } set<pair<long long, long long>> s; for(int i = 0; i < n; i++){ s.emplace(t[i], x[i]); } assert((int) s.size() == n); 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++){ if(a[i] >= 0 && b[i] >= 0) 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"; }