下列代码在洛谷 IDE 上可以正常运行并输出正确答案,但是我在本地使用 VS Code 时试图运行时报 Segmentation Fault,并跳转到 stl_algobase.h 中定义 std::max() 的部分。这是为什么,求大佬解答。
Code:
#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5;
int n,d,k,x[N],s[N];
ll dp[N];
deque<int> q;
bool check(int g) {
memset(dp,0xcf,sizeof(dp));
dp[0]=0;
while(!q.empty()) q.pop_back();
int p=0;
for(int i=1;i<=n;i++) {
// for(int j=0;j<i;j++) {
// if(x[i]-x[j]>=d-g&&x[i]-x[j]<=d+g)
// dp[i]=max(dp[i],dp[j]+s[i]);
// }
while(p<i&&x[i]-x[p]>=max(1,d-g)&&x[i]-x[p]<=d+g) {
while(!q.empty()&&dp[q.back()]<=dp[p]) q.pop_back();
q.push_back(p++);
}
while(!q.empty()&&!(x[i]-x[q.front()]>=max(1,d-g)&&x[i]-x[q.front()]<=d+g)) q.pop_front();
dp[i]=max(dp[i],dp[q.front()]+s[i]);
if(dp[i]>=k) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>d>>k;
for(int i=1;i<=n;i++) cin>>x[i]>>s[i];
int l=0,r=1e9,ans=-1;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) {
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<"\n";
return 0;
}
Data:
Input:
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
Answer:
2