Submission #783656

#	Time	Username	Problem	Language	Result	Execution time	Memory
783656		kshitij_sodani	Long Distance Coach (JOI17_coach)	C++14	71 / 100	107 ms	17776 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'


llo it[200001];
llo dp[200001];
llo xx[200001];
llo pre[200001];
llo pre2[200001];
pair<llo,llo> sect(pair<llo,llo> aa,pair<llo,llo> bb){
	pair<llo,llo> zz={bb.b-aa.b,aa.a-bb.a};
	if(zz.b<0){
		zz.b=-zz.b;
		zz.a=-zz.a;
	}
	return zz;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo x,n,m,w,t;
	cin>>x>>n>>m>>w>>t;
	vector<pair<pair<llo,llo>,llo>> ss;
	llo ans=((x/t)+1)*w;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ss.pb({{it[i]%t,-1},it[i]/t});
	}
	ss.pb({{x%t,-1},x/t});
	for(llo i=0;i<m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		if((aa)<(x%t)){
			ans+=((x/t)*w)+w;
			xx[i]=(x/t);
		}
		else{
			ans+=(((x/t))*w);
			xx[i]=(x/t)-1;
		}
		ss.pb({{aa,xx[i]},bb});
	}
	//cout<<ans<<endl;
	sort(ss.begin(),ss.end());
	dp[0]=0;
	llo ma=0;
	/*for(auto j:ss){
		cout<<j.a.a<<":"<<j.a.b<<":"<<j.b<<endl;
	}*/
	pre[0]=0;
	pre2[0]=0;
	for(int i=0;i<ss.size();i++){
		pre[i+1]=pre[i];
		pre2[i+1]=pre2[i];
		if(ss[i].a.b>=0){
			pre[i+1]+=ss[i].b;
			pre[i+1]-=w*ss[i].a.b;
			pre2[i+1]=pre2[i]+1;
		}
	}
	vector<pair<llo,llo>> ss2;
	vector<pair<llo,llo>> tt;
	for(llo i=0;i<ss.size();i++){
		dp[i+1]=dp[i];
		if(ss[i].a.b>=0){
			pair<llo,llo> cur={-w*pre2[i],-pre[i]-dp[i]};
			while(ss2.size()>=2){
				pair<llo,llo> aa=sect(ss2[ss2.size()-2],ss2.back());
				pair<llo,llo> bb=sect(ss2[ss2.size()-2],cur);
				__int128 xx=(__int128)aa.b*(__int128)bb.a;
				__int128 yy=(__int128)bb.b*(__int128)aa.a;
				if(xx<=yy){
					ss2.pop_back();
					tt.pop_back();
				}
				else{
					break;
				}
				//check if bb<aa
			}
			if(ss2.size()){
				tt.pb(sect(ss2.back(),cur));
			}
			ss2.pb(cur);
		}
		if(ss[i].a.b==-1){
			//llo su=0;
		/*	llo ma=1e18;
			for(auto jj:ss2){
				ma=min(ma,jj.a*(ss[i].b-1)+jj.b);
			}*/
			
			//query for lowest intersection below ss[i].b-1
			llo low=0;
			pair<llo,llo> aa={ss[i].b-1,1};
			for(int j=19;j>=0;j--){
				if(low+(1<<j)<tt.size()){
					pair<llo,llo> bb=tt[low+(1<<j)];
					__int128 xx=(__int128)aa.b*(__int128)bb.a;
					__int128 yy=(__int128)bb.b*(__int128)aa.a;
					if(xx<=yy){
						low+=(1<<j);
					}
					else{
					}
				}
			}
		/*	for(auto j:tt){
			    cout<<j.a<<":"<<j.b<<endl;
			}
			cout<<endl;*/
			for(int j=low-2;j<=low+2;j++){
				if(j<0 or j>=ss2.size()){
					continue;
				}
				ma=min(ma,ss2[j].a*(ss[i].b-1)+ss2[j].b);
			}
			

			dp[i+1]=max(dp[i+1],-ma+(-ss[i].b+1)*pre2[i+1]*w-pre[i+1]);
			/*for(llo j=i-1;j>=0;j--){
				
				llo su=-w*pre2[j]*(-ss[i].b+1);
				//query max here

				pair<llo,llo> cur={-w*pre2[j],-pre[j]-dp[j]};
				//query is (ss[i].b-1)


				//slope is -ss[i].b+1
				//number of type 0 in prefix
				//dp[i+1]=max(dp[i+1],-cot+(-ss[i].b+1)*pre2[i+1]*w-pre[i+1]);

				//dp[i+1]=max(dp[i+1],dp[j]+su+(-ss[i].b+1)*pre2[i+1]*w+pre[j]-pre[i+1]);
			}*/
		}
		ma=max(ma,dp[i+1]);
		//cout<<dp[i+1]<<",";
	}
	//cout<<endl;
	ans-=ma;
	cout<<ans<<endl;
	






	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
coach.cpp:68:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(llo i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~
coach.cpp:102:18: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(low+(1<<j)<tt.size()){
      |        ~~~~~~~~~~^~~~~~~~~~
coach.cpp:118:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     if(j<0 or j>=ss2.size()){
      |               ~^~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29