Submission #998902

#	Time	Username	Problem	Language	Result	Execution time	Memory
998902		DobromirAngelov	Snowball (JOI21_ho_t2)	C++14	100 / 100	61 ms	13908 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second

using namespace std;

const int MAXN=2e5+5;

int n,q;
long long a[MAXN];
pair<long long,int> d[MAXN];
long long ans[MAXN];

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<n;i++)
{
    d[i].fi=a[i+1]-a[i];
    d[i].se=i;
}

sort(d+1,d+n);

long long minPos=0,pos=0,maxPos=0;
int ptr=1;
for(int i=0;i<q;i++)
{
    long long w;
    cin>>w;
    pos+=w;
    if(w>=0)
    {
        maxPos=max(maxPos,pos);
        while(ptr<n && d[ptr].fi<=maxPos-minPos)
        {
            ans[d[ptr].se+1]-=minPos;
            ans[d[ptr].se]+=d[ptr].fi+minPos;
            ptr++;
        }
    }
    else
    {
        minPos=min(minPos, pos);
        while(ptr<n && d[ptr].fi<=maxPos-minPos)
        {
            ans[d[ptr].se]+=maxPos;
            ans[d[ptr].se+1]+=d[ptr].fi-maxPos;
            ptr++;
        }
    }
}
while(ptr<n)
{
    ans[d[ptr].se]+=maxPos;
    ans[d[ptr].se+1]-=minPos;
    ptr++;
}
ans[1]-=minPos;
ans[n]+=maxPos;

for(int i=1;i<=n;i++) cout<<ans[i]<<endl;

return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67