#include <bits/stdc++.h>
using namespace std;
long long L[500005], R[500005], a[500005], b[500005], sum[500005];
vector<pair<long long, long long> > vec[500005];
void updL(long long x, long long y)
{
for (long long i=x; i<=500001; i+=i&(-i))
L[i]=max(L[i], y);
}
void updR(long long x, long long y)
{
for (long long i=x; i<=500001; i+=i&(-i))
R[i]=max(R[i], y);
}
long long qryL(long long x)
{
long long res=-1e18;
for (long long i=x; i; i-=i&(-i))
res=max(res, L[i]);
return res;
}
long long qryR(long long x)
{
long long res=-1e18;
for (long long i=x; i; i-=i&(-i))
res=max(res, R[i]);
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, u, d, s;
cin >> n >> u >> d >> s;
for (long long i=1; i<=n; i++)
{
long long x, y, z;
cin >> x >> y >> z;
vec[x].push_back({y, z});
}
vec[500001].push_back({s, 0});
for (long long i=1; i<=500001; i++)
L[i]=R[i]=-1e18;
updL(s, d*s);
updR(500002-s, -u*s);
for (long long i=1; i<=500001; i++)
{
long long sz=vec[i].size(), mx=-1e18;
sort(vec[i].begin(), vec[i].end());
for (long long j=0; j<sz; j++)
{
long long l=vec[i][j].first, m=vec[i][j].second;
a[j]=max(qryL(l)-d*l+m, qryR(500002-l)+u*l+m);
sum[j]=(j==0)?m:(sum[j-1]+m);
}
for (long long j=0; j<sz; j++)
{
long long l=vec[i][j].first;
mx=max(mx, a[j]+d*l-sum[j]);
b[j]=mx-d*l+sum[j];
}
mx=-1e18;
for (long long j=sz-1; j>=0; j--)
{
long long l=vec[i][j].first;
mx=max(mx, a[j]-u*l-(sum[sz-1]-(j==0?0:sum[j-1])));
b[j]=max(b[j], mx+u*l+sum[sz-1]-(j==0?0:sum[j-1]));
}
if (i==500001)
{
cout << b[0];
return 0;
}
for (long long j=0; j<sz; j++)
{
long long l=vec[i][j].first;
updL(l, b[j]+d*l);
updR(500002-l, b[j]-u*l);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25436 KB |
Output is correct |
2 |
Correct |
6 ms |
25436 KB |
Output is correct |
3 |
Correct |
6 ms |
25436 KB |
Output is correct |
4 |
Correct |
6 ms |
25436 KB |
Output is correct |
5 |
Correct |
7 ms |
25692 KB |
Output is correct |
6 |
Correct |
14 ms |
26024 KB |
Output is correct |
7 |
Correct |
27 ms |
27224 KB |
Output is correct |
8 |
Correct |
46 ms |
28500 KB |
Output is correct |
9 |
Correct |
72 ms |
30188 KB |
Output is correct |
10 |
Correct |
130 ms |
34780 KB |
Output is correct |
11 |
Correct |
135 ms |
34788 KB |
Output is correct |
12 |
Correct |
194 ms |
38228 KB |
Output is correct |
13 |
Correct |
195 ms |
38116 KB |
Output is correct |
14 |
Correct |
235 ms |
41044 KB |
Output is correct |
15 |
Correct |
224 ms |
41044 KB |
Output is correct |
16 |
Correct |
252 ms |
41044 KB |
Output is correct |
17 |
Correct |
5 ms |
25436 KB |
Output is correct |
18 |
Correct |
5 ms |
25436 KB |
Output is correct |
19 |
Correct |
6 ms |
25436 KB |
Output is correct |
20 |
Correct |
6 ms |
25436 KB |
Output is correct |
21 |
Correct |
6 ms |
25436 KB |
Output is correct |
22 |
Correct |
7 ms |
25736 KB |
Output is correct |
23 |
Correct |
7 ms |
25692 KB |
Output is correct |
24 |
Correct |
7 ms |
25692 KB |
Output is correct |
25 |
Correct |
34 ms |
27484 KB |
Output is correct |
26 |
Correct |
63 ms |
29508 KB |
Output is correct |
27 |
Correct |
115 ms |
32576 KB |
Output is correct |
28 |
Correct |
115 ms |
32896 KB |
Output is correct |
29 |
Correct |
146 ms |
34640 KB |
Output is correct |
30 |
Correct |
161 ms |
35776 KB |
Output is correct |