题目描述
诚诚和勤勤去一个由 座小山丘组成的海滨小镇度假。从海岸看去, 座山丘排成一列,第 座山丘到海岸的距离为 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放,但它们的关闭时间是不同的。第 座溜冰场开放 分钟。
诚诚和勤勤将在这里停留 天。他们热爱溜冰,希望在小镇上停留的每一天都以溜冰度过。在第 天的开始,他们距离海岸 米。当滑雪场开放的同时,他们开始他们的溜冰之旅。他们需要走去滑雪场,走路的速度为每分钟 米。
他们的身体非常好,因此他们不需要额外时间来爬山。一旦他们到达山顶的溜冰场,他们可以滑任意长的时间,直到溜冰场关闭。然而,下山并不像上山一样容易,因为下雨,山路非常湿滑,他们需要消耗 的时间走下第 座山。从一座山上下来后,他们可以前往另一座山。
诚诚和勤勤想知道每天他们最长可以溜冰多久的时间。每天他们可以访问任意多座溜冰场。因为他们想用尽可能多的时间溜冰,用尽可能少的时间计算,所以他们向你寻求帮助。帮助他们解决这个问题。
请注意:如果诚诚和勤勤早晨出发的位置就有一座山,他们在山脚。
输入格式
第一行包含两个整数 (),表示山的数量和天数。
接下来 行,第 行包含三个整数 (),分别表示第 座山到海岸的距离、溜冰场的关闭时间和下山所需的时间。
第三行包含 个整数 (),表示诚诚和勤勤第 天出发时到海岸的距离。
输出格式
输出一行 个整数,第 个整数表示第 天诚诚和勤勤可以溜冰的最长时间。
样例输入 #1
样例
样例1输入
复制3 1
3 7 0
6 11 3
10 13 5
1
样例1输出
复制6
样例1解释
诚诚和勤勤在位置 出发,走 分钟到位置 的山,并溜冰 分钟。接着花费 分钟时间下山,继续走 分钟时间到位置 山上的溜冰场,溜冰 分钟后,溜冰场。他们一共溜冰 分钟。
样例2输入
复制3 2
5 10 3
3 6 1
1 5 0
0 3
样例2输出
复制5 8
样例3输入
复制1 3
3 3 3
0 1 2
样例3输出
复制0 1 2
_____________________________________________________________________________
写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,c,s;
int x[1000005];
int y[1000005];
int l[1000005];
struct node{
int l;
int t;
}a[1000005];
bool cmp(node x,node y){return x.l<y.l;}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].t>>s;
l[i]=a[i].l;
}
sort(a+1,a+1+n,cmp);
sort(l+1,l+1+n);
x[0]=y[n+1]=-2e9;
for(int i=1;i<=n;i++){
x[i]=max(a[i].t+a[i].l,x[i-1]);
}
for(int i=n;i>=1;i--){
y[i]=max(a[i].t-a[i].l,y[i+1]);
}
while(m--){
cin>>c;
int xx=lower_bound(l+1,l+n+1,c)-l;
cout<<max(x[xx-1]-c,y[xx]+c)<<" ";
}
}