Submission #333984

#	Time	Username	Problem	Language	Result	Execution time	Memory
333984		kshitij_sodani	Salesman (IOI09_salesman)	C++14	90 / 100	3102 ms	55044 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;
		vector<llo> dis2;
		for(auto j:dis){
			dis2.pb(j);
		}
		vector<llo> mm;
		llo cot=0;
		llo mi=0;
		for(int i=cur-1;i>=cur2;i--){
			mi=min(mi,cot);
			mm.pb(cot-mi);
			if(i>cur2){
				cot+=-(dd+uu)*(ss[i].a.b-ss[i-1].a.b);
				cot+=ss[i].b.a;
			}
		}
		reverse(mm.begin(),mm.end());
		cot=-(llo)1e18;
		mi=0;
		for(int i=cur-1;i>=cur2;i--){
			//mi=min(mi,cot);
			if(i<cur-1){
				cot-=uu*(ss[i+1].a.b-ss[i].a.b);
				cot+=ss[i].b.a;
		//		cot=max(cot,mm[i-cur2]);
			}
			cot=max(cot,(llo)mm[i-cur2]+dis[i-cur2]);
			dis2[i-cur2]=max(dis2[i-cur2],cot-mi);
			
		}

		
		for(int i=cur2;i<cur;i++){
			llo pp=dis[i-cur2];
			llo pop=pp;
			for(int j=i;j>=cur2;j--){
				if(j<i){
					pp-=(ss[j+1].a.b-ss[j].a.b)*(dd+uu);
					pp+=ss[j].b.a;
				}
				pop=max(pop,pp);	
			}
			pp=pop;
			for(int k=i;k<cur;k++){
				if(k>i){
					pp-=dd*(ss[k].a.b-ss[k-1].a.b);
					pp+=ss[k].b.a;
				}
				dis2[k-cur2]=max(dis2[k-cur2],pp);
			}
		}
		for(int i=0;i<dis.size();i++){
			dis[i]=dis2[i];
		}
		/*vector<llo> mm;
		vector<llo> nn;



		llo cp=0;
		llo mi=(llo)1e18;
		llo cur3=0;
		for(llo i=cur2;i<cur;i++){
			mi=min(mi,cp);
			mm.pb(dis[cur3]+cp-mi+ss[i].a.b*dd);
			//nn.pb(dis[cur3]-ss[i].a.b*uu);
			cur3++;
			cp+=ss[i].b.a;
			if(i+1<cur){
				cp+=-(ss[i+1].a.b-ss[i].a.b)*(dd+uu);
			}	
		}
		mi=(llo)1e18;
		cp=0;
		for(llo i=cur-1;i>=cur2;i--){
			cur3--;
			mi=min(mi,cp);
			nn.pb(dis[cur3]+cp-mi-ss[i].a.b*uu);
			cp+=ss[i].b.a;
			if(cur3!=0){
				cp+=-(ss[i].a.b-ss[i-1].a.b)*(dd+uu);
			}
		}
		reverse(nn.begin(),nn.end());
		cur3=0;
		llo ma=mm[0];
		llo su=0;
		for(auto j:dis){
			su+=j;
		}
		vector<llo> dis2;
		for(auto j:dis){
			dis2.pb(j);
		}
		llo sot=su;
	//	cout<<su<<endl;


		for(llo i=cur2;i<cur;i++){
			su-=dis2[cur3];
			ma=max(ma,mm[cur3]+su);
			dis[cur3]=max(dis[cur3],ma-su-ss[i].a.b*dd);
			cur3++;
		}
		ma=nn.back();
		su=sot;
		for(llo i=cur-1;i>=cur2;i--){
			cur3--;
			su-=dis2[cur3];
		//	cout<<(ma-su+ss[i].a.b*uu)<<endl;
			//cout<<ma<<"<"<<su<<"<"<<ss[i].a.b<<"<"<<uu<<endl;
			ma=max(ma,nn[cur3]+su);
			dis[cur3]=max(dis[cur3],ma-su+ss[i].a.b*uu);
		}*/
		/*for(auto j:dis){
			cout<<j<<",,";
		}
		cout<<endl;

		for(auto j:mm){
			cout<<j<<",,";
		}
		cout<<endl;*/


		/*for(auto j:dis){
			cout<<j<<",,";
		}
		cout<<endl;
*/


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

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:157:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |   for(int i=0;i<dis.size();i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 90 / 100