Submission #523321

#	Time	Username	Problem	Language	Result	Execution time	Memory
523321		lucri	Snowball (JOI21_ho_t2)	C++17	33 / 100	213 ms	9412 KiB

Main

#include <iostream>
#include <cmath>
#define ll long long
#define int ll
using namespace std;
int n,q,x[200010],ans[200010],mp[200010],w,cnt,dmin,dmax;
int cb(int b,int e,int val)
{
    if(b>e)
        return b;
    int m=(b+e)/2;
    if(abs(mp[m-1])+abs(mp[m])<val)
        return cb(m+1,e,val);
    return cb(b,m-1,val);
}
main()
{
    cin>>n>>q;
    for(int i=1;i<=n;++i)
    {
        cin>>x[i];
    }
    int dp=0;
    for(int i=1;i<=q;++i)
    {
        cin>>w;
        dp+=w;
        if(dp<0)
        {
            if(mp[cnt]<0)
            {
                if(dp<mp[cnt])
                    mp[cnt]=dp;
            }
            else
            {
                if(dp<dmin)
                {
                    mp[++cnt]=dp;
                    dmin=dp;
                }
            }
        }
        else if(dp>0)
        {
            if(mp[cnt]>0)
            {
                if(dp>mp[cnt])
                    mp[cnt]=dp;
            }
            else
            {
                if(dp>dmax)
                {
                    mp[++cnt]=dp;
                    dmax=dp;
                }
            }
        }
    }
    if(mp[cnt]<0)
    {
        ans[1]-=mp[cnt];
        ans[n]+=mp[cnt-1];
    }
    else
    {
        ans[1]-=mp[cnt-1];
        ans[n]+=mp[cnt];
    }
    for(int i=1;i<n;++i)
    {
        int b=cb(1,cnt,x[i+1]-x[i]);
        if(b>cnt)
        {
            if(mp[cnt]<0)
            {
                ans[i+1]-=mp[cnt];
                ans[i]+=mp[cnt-1];
            }
            else
            {
                ans[i+1]-=mp[cnt-1];
                ans[i]+=mp[cnt];
            }
        }
        else
        {
            if(mp[b]<0)
            {
                ans[i]+=mp[b-1];
                ans[i+1]+=x[i+1]-x[i]-mp[b-1];
            }
            else
            {
                ans[i+1]-=mp[b-1];
                ans[i]+=x[i+1]-x[i]+mp[b-1];
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~

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