分块求条 悬棺
查看原帖
分块求条 悬棺
663195
Z_AuTwT楼主2024/9/25 14:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	register int x=0,f=1;register char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
struct node{
	int l,r,v;
}Arr[100100];
bool Cmp(node a,node b){
	return a.r<b.r;
}
int L[100010],R[100010],Cnt[100010],Min[100010],dp[100010];
main(){
	freopen("P4644_1.in","r",stdin);
	int n=read(),m=read(),e=read();
	for(int i=1;i<=n;i++){
		Arr[i].l=read()-m+2,Arr[i].r=read()-m+2,Arr[i].v=read();
	}
	e-=m;
	e+=2;
	m-=m;
	m+=2;
	int Size=sqrt(e);
	sort(Arr+1,Arr+n+1,Cmp);
	dp[1]=0;
	for(int i=2;i<=e;i++) dp[i]=1e18;
	for(int l=1,r,cnt=1;l<=e;l=r+1,cnt++){
		r=min(Size+l-1,e);
		int MIN=2e18;
		for(int i=l;i<=r;i++) Cnt[i]=cnt,MIN=min(MIN,dp[i]);
		for(int i=l;i<=r;i++) Min[i]=MIN;
		L[cnt]=l;
		R[cnt]=r;
//		cout<<l<<" "<<r<<" "<<Min[l]<<"\n";
	}
	for(int i=1;i<=n;i++){
		int MIN=2e18;
		int LL,RR=((Arr[i].r-1)/Size)*Size;
		if((Arr[i].l-1)%Size==1) LL=Arr[i].l-1;
		else LL=((Arr[i].l-1)/Size+bool((Arr[i].l-1)%Size))+1;
		for(int j=Cnt[LL];j<=Cnt[RR];j++){
			MIN=min(MIN,Min[j]);
		}
		for(int j=Arr[i].l-1;j<LL;j++){
			MIN=min(MIN,dp[j]);
		}
		for(int j=RR+1;j<Arr[i].r;j++){
			MIN=min(MIN,dp[j]);
		}
		dp[Arr[i].r]=MIN+Arr[i].v;
		int TNT=Cnt[Arr[i].r],mmin=2e18;
		for(int j=L[TNT];j<=R[TNT];j++){
			mmin=min(mmin,dp[j]);
		}
		Min[TNT]=mmin;
	}
	if(dp[e]==1e18) puts("-1");
	else cout<<dp[e];
}
2024/9/25 14:18
加载中...