Submission #1020316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020316		AndrijaM	Snowball (JOI21_ho_t2)	C++17	100 / 100	336 ms	12364 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int logn=20;

pair<int,int>lr[maxn];
int n,k,cnt=0;
int x[maxn];

int bs(int n)
{
    int l=0;
    int r=cnt-1;
    while(l<r)
    {
        int mid=l+(r-l+1)/2;
        if(lr[mid].second-lr[mid].first<=n)
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    return l;
}

signed main()
{
    ///freopen("deleg.in","r",stdin);
    ///freopen("deleg.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    int sum=0;
    int l=0;
    int r=0;
    lr[cnt]={0,0};
    cnt++;
    for(int i=0;i<k;i++)
    {
        int a;
        cin>>a;
        sum+=a;
        l=min(l,sum);
        r=max(r,sum);
        if(lr[cnt-1]==pair<int,int>{l,r})continue;
        else
        {
            lr[cnt]={l,r};
            cnt++;
        }
    }
    for(int i=0;i<n;i++)
    {
        int ans=0;
        if(i==n-1)
        {
            ans+=abs(r);
        }
        else
        {
            int len=x[i+1]-x[i];
            int idx=bs(len);
            if(idx==cnt-1 || lr[idx].second==lr[idx+1].second)
            {
                ans+=lr[idx].second;
            }
            else
            {
                ans+=len+lr[idx].first;
            }
        }
        if(i==0)
        {
            ans+=abs(l);
        }
        else
        {
            int len=x[i]-x[i-1];
            int idx=bs(len);
            if(idx==cnt-1 || lr[idx].first==lr[idx+1].first)
            {
                ans+=-lr[idx].first;
            }
            else
            {
                ans+=len-lr[idx].second;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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