Submission #724922

#	Time	Username	Problem	Language	Result	Execution time	Memory
724922		fdnfksd	Snowball (JOI21_ho_t2)	C++14	100 / 100	143 ms	15300 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,x[maxN],mx[maxN],mn[maxN],pre[maxN],ans[maxN];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> x[i];
    mx[0]=mn[0]=0;
    for(int i=1;i<=m;i++)
    {
        ll cc;
        cin >> cc;
        pre[i]=pre[i-1]+cc;
        mx[i]=max(mx[i-1],pre[i]);
        mn[i]=min(mn[i-1],pre[i]);
    }
    for(int i=1;i<n;i++)
    {
        ll low=0,high=m;
        while(low<=high)
        {
            ll mid=low+high>>1;
            if(x[i]+mx[mid]<=x[i+1]+mn[mid]) low=mid+1;
            else high=mid-1;
        }
        if(high==m) ans[i]+=mx[high];
        else
        {
            ans[i]+=max(mx[high],x[i+1]+mn[low]-x[i]);
        }
    }
    for(int i=2;i<=n;i++)
    {
        ll low=0,high=m;
        while(low<=high)
        {
            ll mid=low+high>>1;
            if(x[i]+mn[mid]>=x[i-1]+mx[mid]) low=mid+1;
            else high=mid-1;
        }
        if(high==m) ans[i]+=abs(mn[high]);
        else
        {
            ans[i]+=max(abs(mn[high]),x[i]-(x[i-1]+mx[low]));
        }
    }
    ans[1]+=abs(mn[m]);
    ans[n]+=mx[m];
    for(int i=1;i<=n;i++) cout << ans[i]<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:32:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |             ll mid=low+high>>1;
      |                    ~~~^~~~~
Main.cpp:47:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             ll mid=low+high>>1;
      |                    ~~~^~~~~

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