Submission #320638

#	Time	Username	Problem	Language	Result	Execution time	Memory
320638		kshitij_sodani	Discharging (NOI20_discharging)	C++14	100 / 100	975 ms	344620 KiB

Discharging

//#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;
llo it[1000001];
vector<pair<llo,llo>> ss[4*1000001];
llo ind[1000001*4];
vector<pair<llo,llo>> pre[1000001];
llo dp[1000001];
void build(llo no,llo l,llo r){
	if(l==r){
		pre[r].pb({l,no});
	}
	else{
		pre[r].pb({l,no});
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
	}
}
void re(llo no,llo l,llo r){
//	cout<<no<<":"<<l<<":"<<r<<endl;
	for(llo i=l;i<=r;i++){
		//cout<<no<<":"<<i<<endl;
		pair<llo,llo> xx={(n-i-1),dp[i]};
		while(ss[no].size()>=2){
			llo aa=ss[no].back().b-xx.b;
			llo bb=ss[no].back().a-xx.a;
			llo cc=ss[no][ss[no].size()-2].b-ss[no].back().b;
			llo dd=ss[no][ss[no].size()-2].a-ss[no].back().a;
			aa=-aa;
			cc=-cc;
			long double kk=aa*dd;
			long double mm=bb*cc;
			if(kk<mm){
				ss[no].pop_back();
				continue;
			}
			else{
				break;
			}
		}
		ss[no].pb(xx);
	}
}
llo eval(pair<llo,llo> bb,llo cc){
	return bb.a*cc+bb.b;
}
llo qq=0;
llo query(llo no,llo l,llo r,llo aa,llo bb){

	if(r<aa or l>bb){
		return (llo)1e18;
	}
	if(aa<=l and r<=bb){
		if(ss[no].size()==0){
			re(no,l,r);
		}
	//	cout<<no<<":"<<endl;
		while(ind[no]<(llo)(ss[no].size())-1){
			if(eval(ss[no][ind[no]],qq)>=eval(ss[no][ind[no]+1],qq)){
				ind[no]++;
			}
			else{
				break;
			}
		}
		return eval(ss[no][ind[no]],qq);
	}
	else{
		llo mid=(l+r)/2;
		return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	vector<pair<llo,llo>> ss;
	build(0,0,n-1);
	for(llo i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a<=it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
	//	cout<<i<<endl;
		llo la=-1;
		if(ss.size()){
			la=ss.back().b;
		}
	
		ss.pb({it[i],i});
		dp[i]=ss[0].a*n;
		if(la!=-1){
			dp[i]=min(dp[i],dp[la]);
		}
	
		qq=it[i];
		if(i>0){
			dp[i]=min(dp[i],query(0,0,n-1,max(la,(llo)0),i-1));
		}	
		//cout<<dp[i]<<",";
		if(i==n-1){
			break;
		}
	/*	for(auto j:pre[i]){
			re(j.b,j.a,i);
		}	*/
	}
//	cout<<endl;
	cout<<dp[n-1]<<endl;



















 
 
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28