Pinball的游戏界面由m+2行、n列组成。第一行在顶端。一个球会从第一行的某一列出发,开始垂直下落,界面上有一些漏斗,一共有m个漏斗分别放在第2~m+1行,第i个漏斗的作用是把经过第i+1行且列数在Ai~Bi之间的球,将其移到下一行的第Ci列。 使用第i个漏斗需要支付Di的价钱,你需要保留一些漏斗使得球无论从第一行的哪一列开始放,都只可能到达第m+2行的唯一 一列,求花费的最少代价。
第一行两个数,m和n。m<=100000,2<=n<=1000000000
接下来m行,第i+1行描述第i个漏斗的属性,Ai,Bi,Ci,Di (1<=Ai<=Ci<=Bi<=n, 1<=Di<=1000000000)。
若不存在一种方案能满足条件则输出-1,否则输出最小花费
5 6
3 5 4 8
1 4 3 5
4 6 5 7
5 6 5 3
3 5 4 12
20
我们发现 第一列和第n列 有且仅有一个重复使用的漏斗 就是最后一个
因为如果1和n都已经在一起了,就没有必要再用别的漏斗了
我们定义l[i]为第一列最后使用第i个漏斗的答案
r[i]同理
l[i]=min(a[i].l,a[i].r)+d[i]
最小值用线段树维护
ans=(l[i]+r[i]-d[i])
#include <cstdio>
#include <cstring>
#include <algorithm>
#define L rt<<1
#define R rt<<1|1
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=100005;
typedef long long ll;
ll a[N],b[N],c[N],d[N],q[3*N],k;
ll n,m,h1,h2,i,ans,tr[N*12],l[N],r[N];
ll read(){
ll sum=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') {
sum=sum*10+c-'0';
c=getchar();}
return sum;
}
inline void build(ll rt,ll l,ll r){
tr[rt]=1e17;
if (l==r) return;
ll mid=(l+r)>>1;
build(L,l,mid);
build(R,mid+1,r);
}
inline void update(ll rt,ll l,ll r,ll x,ll z){
if (l==r){
tr[rt]=min(tr[rt],z);
return;}
ll mid=(l+r)>>1;
if (x<=mid) update(L,l,mid,x,z);
else update(R,mid+1,r,x,z);
tr[rt]=min(tr[L],tr[R]);
}
inline ll query(ll rt,ll l,ll r,ll x,ll y){
if (l>=x&&y>=r) return tr[rt];
ll mid=(l+r)>>1;
ll ans=1e17;
if (x<=mid) ans=min(ans,query(L,l,mid,x,y));
if (y>mid) ans=min(ans,query(R,mid+1,r,x,y));
return ans;
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
m=read(); n=read();
fo(i,1,m){
a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
q[++q[0]]=a[i],q[++q[0]]=b[i]; q[++q[0]]=c[i];}
q[++q[0]]=1,q[++q[0]]=n;
sort(q+1,q+q[0]+1);
q[0]=unique(q+1,q+q[0]+1)-q-1;
fo(i,1,m) {
a[i]=lower_bound(q+1,q+q[0]+1,a[i])-q;
b[i]=lower_bound(q+1,q+q[0]+1,b[i])-q;
c[i]=lower_bound(q+1,q+q[0]+1,c[i])-q;
}
h1=1; h2=lower_bound(q+1,q+q[0]+1,n)-q;
build(1,1,h2);
update(1,1,h2,h1,0);
fo(i,1,m){
k=query(1,1,h2,a[i],b[i]);
l[i]=k+d[i];
update(1,1,h2,c[i],l[i]);
}
build(1,1,h2);
update(1,1,h2,h2,0);
fo(i,1,m){
k=query(1,1,h2,a[i],b[i]);
r[i]=k+d[i];
update(1,1,h2,c[i],r[i]);
}
ans=1e17;
fo(i,1,m) ans=min(ans,l[i]+r[i]-d[i]);
if (ans>=1e17) printf("-1\n"); else printf("%lld\n",ans);
}