Submission #233855

#	Time	Username	Problem	Language	Result	Execution time	Memory
233855		kshitij_sodani	Building Bridges (CEOI17_building)	C++17	100 / 100	337 ms	9172 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
vector<pair<llo,llo>> cht;
vector<pair<llo,llo>> cur;
vector<pair<llo,llo>> cht2;
vector<pair<llo,llo>> cht3;
llo bl=350;
llo inf=1e19;
llo val(pair<llo,llo> x,llo y){
	return x.a*y+x.b;
}
bool cmp(pair<llo,llo> x,pair<llo,llo> y){
	if(x.a<y.a){
		return 1;
	}
	else if(y.a<x.a){
		return 0;
	}
	return x.b>y.b;
}
void update(){
	if(cur.size()>bl){
		
		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		llo ind=0;
		llo ind2=0;
		while(ind<cur.size() and ind2<cht.size()){
			if(cur[ind].a>cht[ind2].a or  (cur[ind].a==cht[ind2].a and cur[ind].b>cht[ind2].b )){
				cht2.pb(cur[ind]);
				ind+=1;
			}
			else{
				cht2.pb({cht[ind2]});
				ind2+=1;
			}
		}
		while(ind<cur.size() ){
			cht2.pb(cur[ind]);
			ind+=1;
		}
		while(ind2<cht.size() ){
			cht2.pb(cht[ind2]);
			ind2+=1;
		}
		cht.clear();
		cur.clear();

		for(auto j:cht2){
			while(cht.size()>1){
				if(cht[cht.size()-1].a==j.a){
					cht.pop_back();
					continue;
				}
				
				if((cht[cht.size()-1].a-cht[cht.size()-2].a)*(cht[cht.size()-2].b-j.b)<=(-cht[cht.size()-2].a+j.a)*(cht[cht.size()-2].b-cht[cht.size()-1].b)){
					cht.pop_back();
				}	
				else{
					break;
				}
			}
			cht.pb(j);
		}
		cht2.clear();
		cht3.clear();
		cht3.pb({-inf,-inf});
		for(int j=1;j<cht.size();j++){
			cht3.pb({cht[j].b-cht[j-1].b,cht[j-1].a-cht[j].a});
			if(cht3.back().b<0){
				cht3.back().a=-cht3.back().a;
				cht3.back().b=-cht3.back().b;

			}
		}
	}
}
void insert(llo aa,llo bb){
	cur.pb({aa,bb});
	update();
}

llo bin(llo x){
	llo low=0;
	llo high=cht.size()-1;
	llo ans=inf;
	while(low<high-1){
		int mid=(low+high)/2;
		ans=min(ans,val(cht[mid],x));
		if(x*cht3[mid].b>=cht3[mid].a){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	for(llo i=low;i<high+1;i++){
		ans=min(ans,val(cht[i],x));
	}
	return ans;
}
llo query(llo x){
	llo mi=inf;
	for(auto j:cur){
		mi=min(mi,val(j,x));
	}
	mi=min(mi,bin(x));
	return mi;
}
llo aa[100001];
llo bb[100001];
llo dp[100001];
llo pre[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>aa[i];
	}
	for(llo i=0;i<n;i++){
		cin>>bb[i];
	}
	pre[0]=bb[0];
	for(llo i=1;i<n;i++){
		pre[i]=pre[i-1]+bb[i];
	}
	dp[0]=0;
	insert(-2*aa[0],dp[0]+aa[0]*aa[0]-pre[0]);
	for(llo i=1;i<n;i++){
		dp[i]=query(aa[i])+pre[i-1]+aa[i]*aa[i];
		insert(-2*aa[i],dp[i]+aa[i]*aa[i]-pre[i]);
		
	}
	cout<<dp[n-1]<<endl;





	return 0;
}

Compilation message (stderr)

building.cpp:14:9: warning: overflow in implicit constant conversion [-Woverflow]
 llo inf=1e19;
         ^~~~
building.cpp: In function 'void update()':
building.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cur.size()>bl){
     ~~~~~~~~~~^~~
building.cpp:34:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() and ind2<cht.size()){
         ~~~^~~~~~~~~~~
building.cpp:34:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() and ind2<cht.size()){
                            ~~~~^~~~~~~~~~~
building.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() ){
         ~~~^~~~~~~~~~~
building.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<cht.size() ){
         ~~~~^~~~~~~~~~~
building.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<cht.size();j++){
               ~^~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40