#include <bits/stdc++.h>
using namespace std;
struct SegmentTree
{
vector<int64_t> t;
size_t l;
SegmentTree(size_t n)
{
l = 1 << (32 - __builtin_clz(n));
t = vector<int64_t>(2 * l, INT64_MIN);
}
void update(size_t i, int64_t x)
{
i += l;
t[i] = x;
while (i >>= 1)
t[i] = max(t[2 * i], t[2 * i + 1]);
}
int64_t range_max(size_t i, size_t j)
{
int64_t x = INT64_MIN;
i += l, j += l;
while (i <= j)
{
if (i & 1)
x = max(x, t[i++]);
if (!(j & 1))
x = max(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
};
struct Fair
{
int64_t t, x, v;
};
bool compare_time(Fair const &a, Fair const &b)
{
if (a.t == b.t)
return a.x < b.x;
return a.t < b.t;
}
#define X 500002
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n;
int64_t s, u, d;
cin >> n >> u >> d >> s;
vector<Fair> fairs(n);
for (auto &[t, x, v] : fairs)
cin >> t >> x >> v;
sort(fairs.begin(), fairs.end(), compare_time);
SegmentTree up(X), down(X);
up.update(s, -s * u);
down.update(s, s * d);
vector<int64_t> best_value(n, INT64_MIN);
for (size_t i = 0; i < n;)
{
size_t m = 1;
while (i + m < n && fairs[i + m].t == fairs[i].t)
m++;
for (size_t j = i; j < i + m; ++j)
{
int64_t dx = INT64_MIN;
if (down.range_max(0, fairs[j].x) != INT64_MIN)
dx = max(dx, down.range_max(0, fairs[j].x) - fairs[j].x * d);
if (up.range_max(fairs[j].x, X - 1) != INT64_MIN)
dx = max(dx, up.range_max(fairs[j].x, X - 1) + fairs[j].x * u);
if (dx != INT64_MIN)
{
down.update(fairs[j].x, dx + fairs[j].v + fairs[j].x * d);
best_value[j] = dx + fairs[j].v;
}
}
for (size_t j = i; j < i + m; ++j)
down.update(fairs[j].x, INT64_MIN);
for (size_t j = i + m - 1; j >= i && j < i + m; --j)
{
int64_t dx = INT64_MIN;
if (down.range_max(0, fairs[j].x) != INT64_MIN)
dx = max(dx, down.range_max(0, fairs[j].x) - fairs[j].x * d);
if (up.range_max(fairs[j].x, X - 1) != INT64_MIN)
dx = max(dx, up.range_max(fairs[j].x, X - 1) + fairs[j].x * u);
if (dx != INT64_MIN)
{
up.update(fairs[j].x, dx + fairs[j].v - fairs[j].x * u);
best_value[j] = max(best_value[j], dx + fairs[j].v);
}
}
for (size_t j = i; j < i + m; ++j)
{
down.update(fairs[j].x, best_value[j] + fairs[j].x * d);
up.update(fairs[j].x, best_value[j] - fairs[j].x * u);
}
i += m;
}
cout << max(down.range_max(0, s) - s * d, up.range_max(s, X - 1) + s * u) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
16724 KB |
Output is correct |
2 |
Correct |
9 ms |
16724 KB |
Output is correct |
3 |
Correct |
7 ms |
16724 KB |
Output is correct |
4 |
Correct |
8 ms |
16728 KB |
Output is correct |
5 |
Correct |
13 ms |
16852 KB |
Output is correct |
6 |
Correct |
31 ms |
17320 KB |
Output is correct |
7 |
Correct |
67 ms |
18260 KB |
Output is correct |
8 |
Correct |
115 ms |
19788 KB |
Output is correct |
9 |
Correct |
156 ms |
21380 KB |
Output is correct |
10 |
Correct |
284 ms |
26148 KB |
Output is correct |
11 |
Correct |
335 ms |
26132 KB |
Output is correct |
12 |
Correct |
434 ms |
29264 KB |
Output is correct |
13 |
Correct |
427 ms |
29264 KB |
Output is correct |
14 |
Correct |
537 ms |
32280 KB |
Output is correct |
15 |
Correct |
480 ms |
32404 KB |
Output is correct |
16 |
Correct |
553 ms |
32392 KB |
Output is correct |
17 |
Correct |
7 ms |
16724 KB |
Output is correct |
18 |
Correct |
11 ms |
16724 KB |
Output is correct |
19 |
Correct |
8 ms |
16680 KB |
Output is correct |
20 |
Correct |
10 ms |
16724 KB |
Output is correct |
21 |
Correct |
11 ms |
16724 KB |
Output is correct |
22 |
Correct |
11 ms |
16788 KB |
Output is correct |
23 |
Correct |
10 ms |
16904 KB |
Output is correct |
24 |
Correct |
11 ms |
16852 KB |
Output is correct |
25 |
Correct |
107 ms |
19952 KB |
Output is correct |
26 |
Correct |
225 ms |
22996 KB |
Output is correct |
27 |
Correct |
336 ms |
27608 KB |
Output is correct |
28 |
Correct |
356 ms |
27604 KB |
Output is correct |
29 |
Correct |
540 ms |
32392 KB |
Output is correct |
30 |
Correct |
522 ms |
32408 KB |
Output is correct |