#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int n,u,d,s,dp[500005][2],seg_pos[500005];
pair<int,pair<int,int>> e[500005];
pair<int,int> pos[500005];
int seg1[2][2000005],seg2[2][2000005];
//seg1 , upstream seg2 , downstream
//seg 1D-> dp[k][0], seg 2D -> dp[k][1]
void build(int id,int x,int y){
seg1[0][id]=seg1[1][id]=LLONG_MIN;
seg2[0][id]=seg2[1][id]=LLONG_MIN;
if (x==y) return;
int mid=(x+y)/2;
build(id*2,x,mid);
build(id*2+1,mid+1,y);
}
void uprng(int id,int x,int y,int p,int type,int v){
if (x==y) seg1[type][id]=v;
else if (p<=(x+y)/2) uprng(id*2,x,(x+y)/2,p,type,v);
else uprng(id*2+1,(x+y)/2+1,y,p,type,v);
if (x!=y) seg1[type][id]=max(seg1[type][id*2],seg1[type][id*2+1]);
}
void downrng(int id,int x,int y,int p,int type,int v){
if (x==y) seg2[type][id]=v;
else if (p<=(x+y)/2) downrng(id*2,x,(x+y)/2,p,type,v);
else downrng(id*2+1,(x+y)/2+1,y,p,type,v);
if (x!=y) seg2[type][id]=max(seg2[type][id*2],seg2[type][id*2+1]);
}
int upqry(int id,int x,int y,int l,int r,int type){
if (x>y || y<l || x>r) return LLONG_MIN;
if (l<=x && y<=r) return seg1[type][id];
int mid=(x+y)/2;
return max(upqry(id*2,x,mid,l,r,type),upqry(id*2+1,mid+1,y,l,r,type));
}
int downqry(int id,int x,int y,int l,int r,int type){
if (x>y || y<l || x>r) return LLONG_MIN;
if (l<=x && y<=r) return seg2[type][id];
int mid=(x+y)/2;
return max(downqry(id*2,x,mid,l,r,type),downqry(id*2+1,mid+1,y,l,r,type));
}
signed main(){
cin>>n>>u>>d>>s;
for (int i=1;i<=n;i++){
cin>>e[i].f>>e[i].s.f>>e[i].s.s;
}
sort(e+1,e+1+n);
for (int i=1;i<=n;i++) pos[i]=make_pair(e[i].s.f,i);
sort(pos+1,pos+1+n);
build(1,1,n);
for (int i=1;i<=n;i++) seg_pos[pos[i].s]=i;
int ans=0;
for (int i=1;i<=n;){
int pt=i;
while (pt+1<=n && e[pt+1].f==e[i].f) ++pt;
for (int j=i;j<=pt;j++){
if (e[j].s.f>=s) dp[j][0]=dp[j][1]=e[j].s.s-(e[j].s.f-s)*d;
else dp[j][0]=dp[j][1]=e[j].s.s-(s-e[j].s.f)*u;
int l=1; int r=n;
while (l!=r){
int mid=(l+r)/2;
if (pos[mid].f>=e[j].s.f) r=mid;
else l=mid+1;
}
int lt=max(upqry(1,1,n,r,n,0),upqry(1,1,n,r,n,1));
int rt=max(downqry(1,1,n,1,r-1,0),downqry(1,1,n,1,r-1,1));
if (lt!=LLONG_MIN) dp[j][0]=max(dp[j][0],lt+e[j].s.f*u+e[j].s.s);
if (rt!=LLONG_MIN) dp[j][0]=max(dp[j][0],rt-e[j].s.f*d+e[j].s.s);
dp[j][1]=dp[j][0];
}
for (int j=i;j<=pt;j++){
int l=1; int r=n;
while (l!=r){
int mid=(l+r)/2;
if (pos[mid].f>=e[j].s.f) r=mid;
else l=mid+1;
}
int lt=upqry(1,1,n,r,n,0);
int rt=downqry(1,1,n,1,r-1,0);
if (lt!=LLONG_MIN) dp[j][0]=max(dp[j][0],lt+e[j].s.f*u+e[j].s.s);
if (rt!=LLONG_MIN) dp[j][0]=max(dp[j][0],rt-e[j].s.f*d+e[j].s.s);
if (e[j].s.f>=s) ans=max(ans,dp[j][0]-(e[j].s.f-s)*u);
else ans=max(ans,dp[j][0]-(s-e[j].s.f)*d);
uprng(1,1,n,seg_pos[j],0,dp[j][0]-e[j].s.f*u);
downrng(1,1,n,seg_pos[j],0,dp[j][0]+e[j].s.f*d);
//cout<<seg_pos[j]<<" "<<pos[seg_pos[j]].f<<"\n";
}
reverse(e+i,e+pt+1); reverse(dp+i,dp+pt+1);
reverse(seg_pos+i,seg_pos+pt+1);
for (int j=i;j<=pt;j++){
int l=1; int r=n;
while (l!=r){
int mid=(l+r)/2;
if (pos[mid].f>=e[j].s.f) r=mid;
else l=mid+1;
}
int lt=upqry(1,1,n,r,n,1);
int rt=downqry(1,1,n,1,r-1,1);
if (lt!=LLONG_MIN) dp[j][1]=max(dp[j][1],lt+e[j].s.f*u+e[j].s.s);
if (rt!=LLONG_MIN) dp[j][1]=max(dp[j][1],rt-e[j].s.f*d+e[j].s.s);
if (e[j].s.f>=s) ans=max(ans,dp[j][1]-(e[j].s.f-s)*u);
else ans=max(ans,dp[j][1]-(s-e[j].s.f)*d);
uprng(1,1,n,seg_pos[j],1,dp[j][1]-e[j].s.f*u);
downrng(1,1,n,seg_pos[j],1,dp[j][1]+e[j].s.f*d);
}
reverse(e+i,e+pt+1); reverse(dp+i,dp+pt+1);
reverse(seg_pos+i,seg_pos+pt+1);
//for (int j=i;j<=pt;j++) cout<<dp[j][0]<<" "<<dp[j][1]<<"\n";
i=pt+1;
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
5 ms |
596 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1240 KB |
Output is correct |
| 6 |
Correct |
57 ms |
3940 KB |
Output is correct |
| 7 |
Correct |
164 ms |
8380 KB |
Output is correct |
| 8 |
Correct |
363 ms |
16496 KB |
Output is correct |
| 9 |
Correct |
593 ms |
28444 KB |
Output is correct |
| 10 |
Correct |
1060 ms |
56600 KB |
Output is correct |
| 11 |
Correct |
1281 ms |
57312 KB |
Output is correct |
| 12 |
Correct |
1737 ms |
64276 KB |
Output is correct |
| 13 |
Correct |
1794 ms |
64684 KB |
Output is correct |
| 14 |
Correct |
2199 ms |
65536 KB |
Output is correct |
| 15 |
Correct |
1950 ms |
65536 KB |
Output is correct |
| 16 |
Correct |
2243 ms |
65536 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
2 ms |
468 KB |
Output is correct |
| 20 |
Correct |
7 ms |
796 KB |
Output is correct |
| 21 |
Correct |
7 ms |
724 KB |
Output is correct |
| 22 |
Correct |
17 ms |
1248 KB |
Output is correct |
| 23 |
Correct |
12 ms |
1220 KB |
Output is correct |
| 24 |
Correct |
13 ms |
1236 KB |
Output is correct |
| 25 |
Correct |
325 ms |
16248 KB |
Output is correct |
| 26 |
Correct |
703 ms |
31996 KB |
Output is correct |
| 27 |
Correct |
1246 ms |
59596 KB |
Output is correct |
| 28 |
Correct |
1459 ms |
60556 KB |
Output is correct |
| 29 |
Correct |
2054 ms |
65536 KB |
Output is correct |
| 30 |
Correct |
1995 ms |
65536 KB |
Output is correct |
