C++14(g++5.4) 解法, 执行用时: 234ms, 内存消耗: 22008K, 提交时间: 2020-09-27 15:10:40
#include<bits/stdc++.h>
using namespace std;
int i,n,m,t,L=1,T[300005],a[100005],b[100005],c[100005],d[100005];
long long j,k,y,ans=1e18,Min[1200005][2];
void update(int L,int R,int l,int r,int x,bool f)
{
if(l<=L&&R<=r)
{
Min[x][f]=min(Min[x][f],y);
return;
}
int M=(L+R)>>1;
if(M>=l)update(L,M,l,r,x<<1,f);
if(M<r)update(M+1,R,l,r,x<<1|1,f);
Min[x][f]=min(Min[x<<1][f],Min[x<<1|1][f]);
}
void search(int L,int R,int l,int r,int x,bool f)
{
if(l<=L&&R<=r)
{
y=min(Min[x][f],y);
return;
}
int M=(L+R)>>1;
if(M>=l)search(L,M,l,r,x<<1,f);
if(M<r)search(M+1,R,l,r,x<<1|1,f);
}
int main()
{
scanf("%d%d",&n,&m);
memset(Min,0x7f,sizeof(Min));
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
T[L++]=a[i],T[L++]=b[i],T[L++]=c[i];
}
sort(T+1,T+L);
for(i=t=2;i<L;i++)if(T[i]!=T[i-1])T[t++]=T[i];
t--,y=0,update(1,t,1,1,1,0),update(1,t,t,t,1,1);
for(i=1;i<=n;i++)
{
a[i]=lower_bound(T+1,T+1+t,a[i])-T;
b[i]=lower_bound(T+1,T+1+t,b[i])-T;
c[i]=lower_bound(T+1,T+1+t,c[i])-T;
y=1e18,search(1,t,a[i],b[i],1,0),j=y;
y=1e18,search(1,t,a[i],b[i],1,1),k=y;
y=j+d[i],update(1,t,c[i],c[i],1,0);
y=k+d[i],update(1,t,c[i],c[i],1,1);
ans=min(ans,j+k+d[i]);
}
if(ans==1e18)ans=-1;
printf("%lld\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 232ms, 内存消耗: 21880K, 提交时间: 2020-07-31 18:14:25
#include<bits/stdc++.h>
using namespace std;
int i,n,m,t,L=1,T[300005],a[100005],b[100005],c[100005],d[100005];
long long j,k,y,ans=1e18,Min[1200005][2];
void update(int L,int R,int l,int r,int x,bool f)
{
if(l<=L&&R<=r)
{
Min[x][f]=min(Min[x][f],y);
return;
}
int M=(L+R)>>1;
if(M>=l)update(L,M,l,r,x<<1,f);
if(M<r)update(M+1,R,l,r,x<<1|1,f);
Min[x][f]=min(Min[x<<1][f],Min[x<<1|1][f]);
}
void search(int L,int R,int l,int r,int x,bool f)
{
if(l<=L&&R<=r)
{
y=min(Min[x][f],y);
return;
}
int M=(L+R)>>1;
if(M>=l)search(L,M,l,r,x<<1,f);
if(M<r)search(M+1,R,l,r,x<<1|1,f);
}
int main()
{
scanf("%d%d",&n,&m);
memset(Min,0x7f,sizeof(Min));
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
T[L++]=a[i],T[L++]=b[i],T[L++]=c[i];
}
sort(T+1,T+L);
for(i=t=2;i<L;i++)if(T[i]!=T[i-1])T[t++]=T[i];
t--,y=0,update(1,t,1,1,1,0),update(1,t,t,t,1,1);
for(i=1;i<=n;i++)
{
a[i]=lower_bound(T+1,T+1+t,a[i])-T;
b[i]=lower_bound(T+1,T+1+t,b[i])-T;
c[i]=lower_bound(T+1,T+1+t,c[i])-T;
y=1e18,search(1,t,a[i],b[i],1,0),j=y;
y=1e18,search(1,t,a[i],b[i],1,1),k=y;
y=j+d[i],update(1,t,c[i],c[i],1,0);
y=k+d[i],update(1,t,c[i],c[i],1,1);
ans=min(ans,j+k+d[i]);
}
if(ans==1e18)ans=-1;
printf("%lld\n",ans);
return 0;
}
到
列，如果rainy向下走一层后，正好走到这一楼的已启用的魔法装置的作用区域，她就会被传送到第
列，继续往下走，否则她将保持原来所在列继续向下走。
的魔法值，虽然魔法少女wjy的魔法值很多，但她还是想知道，如果她想使，rainy无论从第一层的哪个房间开始走下，都能走到同一列里面，所至少要花费的魔法值。和
。
接下来n行 每行四个正整数。
保证