Submission #964393

#	Time	Username	Problem	Language	Result	Execution time	Memory
964393		maxFedorchuk	Snowball (JOI21_ho_t2)	C++17	100 / 100	82 ms	18836 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10;
long long x[MX],w[MX],ans[MX];

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    for(long long i=1;i<=n;i++)
    {
        cin>>x[i];
    }

    for(long long i=1;i<=m;i++)
    {
        cin>>w[i];
        w[i]+=w[i-1];
    }

    vector < long long > imt;
    vector < long long > sum;
    vector < long long > mnz;
    vector < long long > mxz;
    imt.push_back(0);
    mnz.push_back(0);
    mxz.push_back(0);

    long long mn=0,mx=0;
    for(long long i=1;i<=m;i++)
    {
        if(w[i]<mn)
        {
            imt.push_back(w[i]);
            mnz.push_back(w[i]);
            mxz.push_back(mxz.back());
            mn=w[i];
        }

        if(w[i]>mx)
        {
            imt.push_back(w[i]);
            mnz.push_back(mnz.back());
            mxz.push_back(w[i]);
            mx=w[i];
        }
    }

    m=imt.size()-1;
    for(long long i=0;i<=m;i++)
    {
        sum.push_back(llabs(mxz[i])+llabs(mnz[i]));
    }

    for(long long i=2;i<=n;i++)
    {
        long long l=0,r=m+1;

        while(l+1<r)
        {
            long long mid=(l+r)/2;
            if(sum[mid]<=(x[i]-x[i-1]))
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }

        ans[i-1]+=llabs(mxz[l]);
        ans[i]+=llabs(mnz[l]);

        if(r==m+1)
        {
            continue;
        }

        if(imt[r]<0)
        {
            ans[i]+=(x[i]-x[i-1])-sum[l];
        }
        else
        {
            ans[i-1]+=(x[i]-x[i-1])-sum[l];
        }
    }

    ans[1]+=llabs(mnz[m]);
    ans[n]+=llabs(mxz[m]);

    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<"\n";
    }

    return 0;
}

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