Submission #333760

#	Time	Username	Problem	Language	Result	Execution time	Memory
333760		kshitij_sodani	Salesman (IOI09_salesman)	C++14	60 / 100	1156 ms	61248 KiB

salesman

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,uu,dd,stt;
llo ind[500001];
llo tree[2][500001*4];
vector<pair<pair<llo,llo>,pair<llo,llo>>> ss;
vector<pair<pair<llo,llo>,pair<llo,llo>>> tt;
void build(llo no,llo l,llo r,llo cot){
	if(l==r){

		tree[cot][no]=-(llo)1e9;
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid,cot);
		build(no*2+2,mid+1,r,cot);
		tree[cot][no]=max(tree[cot][no*2+1],tree[cot][no*2+2]);
	}
}
void update(llo no,llo l,llo r,llo i,llo val,llo cot){
	if(l==r){
		//cout<<i<<"<<"<<val<<"<<"<<cot<<endl;
		tree[cot][no]=val;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,val,cot);
		}
		else{
			update(no*2+2,mid+1,r,i,val,cot);
		}
		tree[cot][no]=max(tree[cot][no*2+1],tree[cot][no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo cot){
	if(bb<l or aa>r){
		return -1e9;
	}
	if(aa<=l and r<=bb){
		//cout<<cot<<"<<<<<<<<<<<<<<"<<endl;
		//cout<<l<<"<<"<<r<<",,"<<tree[cot][no]<<endl;
		return tree[cot][no];
	}
	else{
		llo mid=(l+r)/2;
		return max(query(no*2+1,l,mid,aa,bb,cot),query(no*2+2,mid+1,r,aa,bb,cot));
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>uu>>dd>>stt;
	
	for(llo i=0;i<n;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		ss.pb({{aa,bb},{cc,i}});
		tt.pb({{bb,aa},{cc,i}});
	}
	sort(ss.begin(),ss.end());
	sort(tt.begin(),tt.end());
	for(llo j=0;j<n;j++){
		ind[tt[j].b.b]=j;
	}
	llo cur=0;
	build(0,0,n-1,0);
	build(0,0,n-1,1);
	llo ans=0;
	while(cur<n){
		llo cur2=cur;
		while(cur<n){
			if(ss[cur].a.a==ss[cur2].a.a){
				cur++;
			}
			else{
				break;
			}
		}
		vector<llo> kk;
		vector<llo> dis;
		for(llo i=cur2;i<cur;i++){
			llo val=0;
			if(ss[i].a.b<stt){
				val+=(stt-ss[i].a.b)*uu;
			}
			else{
				val+=(ss[i].a.b-stt)*dd;
			}
			val=-val;
			//cout<<query(0,0,n-1,ind[ss[i].b.b],n-1,0)<<endl;
			val=max(val,query(0,0,n-1,ind[ss[i].b.b],n-1,0)+uu*ss[i].a.b);
			val=max(val,query(0,0,n-1,0,ind[ss[i].b.b],1)-dd*ss[i].a.b);
		
			val+=ss[i].b.a;
			dis.pb(val);
		}
		llo cur3=0;
		for(llo i=cur2;i<cur;i++){
			llo val=0;
			if(ss[i].a.b<stt){
				val+=(stt-ss[i].a.b)*dd;
			}
			else{
				val+=(ss[i].a.b-stt)*uu;
			}
			val=-val;
			val+=dis[cur3];
		//	cout<<ss[i].b.b<<":"<<dis[cur3]<<"::"<<val<<":"<<ind[ss[i].b.b]<<endl;
			ans=max(ans,val);
			//if(ss[i].b.b!=3){
				update(0,0,n-1,ind[ss[i].b.b],dis[cur3]-ss[i].a.b*uu,0);
				update(0,0,n-1,ind[ss[i].b.b],dis[cur3]+ss[i].a.b*dd,1);
			//}
			cur3++;
		}
	}
	cout<<ans<<endl;













 
	return 0;
}

• Subtask 1: 60 / 100