#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e17;
ll n,q,x[200005],w[200005],smax[200005],smin[200005],sol[200005];
ll getfst(ll need)
{
assert(need!=0);
if(need>0)
{
ll st=1;
ll dr=q;
ll poz=INF;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(smax[mij]>need)
{
poz=mij;
dr=mij-1;
}
else
st=mij+1;
}
return poz;
}
else
{
ll st=1;
ll dr=q;
ll poz=INF;
while(st<=dr)
{
ll mij=(st+dr)/2;
if(smin[mij]<need)
{
poz=mij;
dr=mij-1;
}
else
st=mij+1;
}
return poz;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(ll i=1;i<=n;i++)
cin>>x[i];
for(ll i=1;i<=q;i++)
cin>>w[i];
smax[1]=w[1];
smin[1]=w[1];
for(ll i=2;i<=q;i++)
{
w[i]=w[i-1]+w[i];
smax[i]=max(smax[i-1],w[i]);
smin[i]=min(smin[i-1],w[i]);
}
for(ll i=1;i<n;i++)
{
ll p1=x[i];
ll p2=x[i+1];
ll st=p1+1;
ll dr=p2;
ll nr=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
ll needL=mij-p1;
ll needR=(mij-1)-p2;
ll fstL=getfst(needL);
ll fstR=getfst(needR);
if(fstL<fstR&&fstL<=q)
{
nr=mij-p1;
st=mij+1;
}
else
dr=mij-1;
}
sol[i]+=nr;
st=p1;
dr=p2-1;
nr=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
ll needL=mij+1-p1;
ll needR=mij-p2;
ll fstL=getfst(needL);
ll fstR=getfst(needR);
if(fstR<fstL&&fstR<=q)
{
nr=p2-mij;
dr=mij-1;
}
else
st=mij+1;
}
sol[i+1]+=nr;
}
sol[1]-=smin[q];
sol[n]+=smax[q];
for(ll i=1;i<=n;i++)
cout<<sol[i]<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
