Submission

Score: 0

User: Newtonabc

Problemset: อโมกุส

Language: cpp

Time: 0.000 second

Submitted On: 2024-09-28 21:11:33

#include <vector>
#include <climits>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mp make_pair
using namespace std;
const int S=5e4+10;
const int N=1<<17;
int n,m,k,sz,rnk[S];
long long dist[S],mn[S],a[S];
bool vs[S];
vector<pair<long long,int> > adj[S];
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
struct stree{
	long long s[N];
	void build(int l,int r,int idx){
		s[idx]=1e18;
		if(l==r) return;
		int m=(l+r)/2;
		build(l,m,idx*2);
		build(m+1,r,idx*2+1);
	}
	void update(int l,int r,int idx,int x,long long val){
		if(x<l || x>r) return;
		if(l==r){
			s[idx]=min(s[idx],val);
			return;
		}
		int m=(l+r)/2;
		update(l,m,idx*2,x,val);
		update(m+1,r,idx*2+1,x,val);
		s[idx]=min(s[idx*2],s[idx*2+1]);
	}
	long long query(int l,int r,int idx,int a,int b){
		if(b<l || a>r) return 1e18;
		if(a<=l && b>=r) return s[idx];
		int m=(l+r)/2;
		return min(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
	}
}s1,s2;
void dijkstra(){
    for(int i=0;i<=n;i++) vs[i]=false;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vs[u]) continue;
        vs[u]=true;
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].second;
            long long w=adj[u][i].first;
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                q.push(mp(dist[v],v));
            }
        }
    }
}
long long minimum_energy(int N, int M, int K, vector<int> A, vector<int> L, 
                         vector<int> R, vector<int> C){
    n=N,m=M,k=K;
    for(int i=1;i<=n;i++){
        a[i]=A[i-1];
        adj[i-1].push_back(mp(a[i],i));
        adj[i].push_back(mp(a[i],i-1));
    }
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    sz=A.size();
    for(int i=1;i<=n;i++) rnk[i]=lower_bound(A.begin(),A.end(),a[i])-A.begin()+1;
    for(int i=1;i<=m;i++){
        adj[L[i-1]].push_back(mp(C[i-1],R[i-1]+1));
        adj[R[i-1]+1].push_back(mp(C[i-1],L[i-1]));
    }
    for(int i=1;i<=n;i++) dist[i]=LLONG_MAX;
    q.push(mp(0,0));
    dijkstra();
    for(int lp=0;lp<k;lp++){
	    for(int i=1;i<=n;i++) mn[i]=LLONG_MAX;
	    s1.build(0,sz,1),s2.build(0,sz,1);
	    for(int i=1;i<=n;i++){
	    	long long tmpa,tmpb;
	    	s1.update(0,sz,1,rnk[i],dist[i-1]-a[i]*a[i]);
	    	s2.update(0,sz,1,rnk[i],dist[i-1]+a[i]*a[i]);
	    	tmpa=s1.query(0,sz,1,1,rnk[i])+a[i]*a[i];
	    	tmpb=s2.query(0,sz,1,rnk[i],n)-a[i]*a[i];
	    	mn[i]=min(tmpa,tmpb);
		}
		s1.build(0,sz,1),s2.build(0,sz,1);
		for(int i=n;i>=1;i--){
			long long tmpa,tmpb;
			s1.update(0,sz,1,rnk[i],dist[i]-a[i]*a[i]);
			s2.update(0,sz,1,rnk[i],dist[i]+a[i]*a[i]);
			tmpa=s1.query(0,sz,1,1,rnk[i])+a[i]*a[i];
			tmpb=s2.query(0,sz,1,rnk[i],n)-a[i]*a[i];
			mn[i-1]=min(mn[i-1],min(tmpa,tmpb));
		}
		/*for(int i=0;i<=n;i++) cout<<rnk[i] <<" ";
		cout<<"\n";
		for(int i=0;i<=n;i++) cout<<mn[i] <<" ";
		cout<<"\n";*/
		for(int i=1;i<=n;i++){
			if(mn[i]<dist[i]){
				dist[i]=mn[i];
				q.push(mp(dist[i],i));
			}
		}
		dijkstra();
	}
    return dist[n];
}