Submission #718732

#	Time	Username	Problem	Language	Result	Execution time	Memory
718732		starplat	Salesman (IOI09_salesman)	C++14	100 / 100	2243 ms	65536 KiB

salesman

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

• Subtask 1: 100 / 100