已经 #define int long long 了。
思路大概是把每次刮的风存下来,计算从开始到当前时间每个雪球相对于初始位置的偏移量。
然后二分断点找出最后一个满足相邻雪球不重叠的时间,如果下次刮向右的风,那么应该是由于下次刮风导致的整个相邻两个球的区间被完全覆盖;向左同理。
但是 WA 在了十四万行,不是很能理解。
但是我认为题解的写法和我的等价啊/kk
#include<bits/stdc++.h>
#define int long long
#define INF INT32_MAX
#define INFll INT64_MAX
using namespace std;
const int N=1e6+10;
int n,m;
int L[N],R[N],a[N];
int ans[N];
void work(int x,int len)
{
if(L[m]+R[m]<=len)
{
ans[x]+=R[m];
ans[x+1]+=L[m];
return;
}
int l=1,r=m,q=-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(L[mid]+R[mid]<=len) l=mid;
else r=mid-1;
}
q=l;
if(L[q]==L[q+1])
ans[x]+=len-L[q],ans[x+1]+=L[q];
else ans[x]+=R[q],ans[x+1]+=len-R[q];
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int tmp=0;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;tmp+=x;
L[i]=max(L[i-1],-tmp);
R[i]=max(R[i-1],tmp);
}
ans[1]+=L[m],ans[n]+=R[m];
for(int i=1;i<n;i++) work(i,a[i+1]-a[i]);
for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
return 0;
}
感激不尽。