제출 #553574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553574		andrei_boaca	Snowball (JOI21_ho_t2)	C++17	33 / 100	1814 ms	10232 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e9;
ll n,q,x[200005],w[200005],smax[200005],smin[200005],sol[200005];
ll getfst(ll need)
{
    assert(need!=0);
    if(need>=0)
    {
        ll st=1;
        ll dr=q;
        ll poz=INF;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(smax[mij]>=need)
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        return poz;
    }
    else
    {
        ll st=1;
        ll dr=q;
        ll poz=INF;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(smin[mij]<=need)
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        return poz;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>x[i];
    for(int i=1;i<=q;i++)
        cin>>w[i];
    smax[1]=w[1];
    smin[1]=w[1];
    for(int i=2;i<=q;i++)
    {
        w[i]=w[i-1]+w[i];
        smax[i]=max(smax[i-1],w[i]);
        smin[i]=min(smin[i-1],w[i]);
    }
    for(int i=1;i<n;i++)
    {
        ll p1=x[i];
        ll p2=x[i+1];
        ll st=p1+1;
        ll dr=p2;
        ll nr=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            ll needL=mij-p1;
            ll needR=(mij-1)-p2;
            ll fstL=getfst(needL);
            ll fstR=getfst(needR);
            if(fstL<fstR&&fstL!=INF)
            {
                nr=mij-p1;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        sol[i]+=nr;
        st=p1;
        dr=p2-1;
        nr=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            ll needL=mij+1-p1;
            ll needR=mij-p2;
            ll fstL=getfst(needL);
            ll fstR=getfst(needR);
            if(fstR<fstL&&fstR!=INF)
            {
                nr=p2-mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        sol[i+1]+=nr;
    }
    sol[1]-=smin[q];
    sol[n]+=smax[q];
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

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