結果

問題 No.2859 Falling Balls
ユーザー dyktr_06
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
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";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0