Submission #692603

#	Time	Username	Problem	Language	Result	Execution time	Memory
692603		owoovo	Snowball (JOI21_ho_t2)	C++14	100 / 100	264 ms	12712 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
pair<ll,ll> BITmax[200010],BITmin[200010];
ll ori[200010],ans[200010]={};
void modify(pair<ll,ll> x,ll p){
    while(p<=200005){
        if(BITmax[p].first<x.first){
            BITmax[p]=x;
        }
        if(BITmin[p].first>x.first){
            BITmin[p]=x;
        }
        p+=p&(-p);
    }
    return ;
}
pair<pair<ll,ll>,pair<ll,ll>> q(ll p){
    pair<ll,ll> ansmax={0,0},ansmin={0,0};
    while(p){
        if(ansmax.first<BITmax[p].first){
            ansmax=BITmax[p];
        }
        if(ansmin.first>BITmin[p].first){
            ansmin=BITmin[p];
        }
        p-=p&(-p);
    }
    return make_pair(ansmax,ansmin);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>ori[i];
    }
    ll now=0;
    for(ll i=1;i<=m;i++){
        ll a;
        cin>>a;
        now+=a;
        modify(make_pair(now,i),i);
    }
    ll l=q(200005).second.first,r=q(200005).first.first;
    ans[1]+=abs(l);
    ans[n]+=abs(r);
    for(ll i=1;i<n;i++){
        ll dis=ori[i+1]-ori[i];
        if(ori[i+1]-ori[i]>=abs(l)+abs(r)){
            ans[i]+=abs(r);
            ans[i+1]+=abs(l);
        }else{ 
            ll L=0,R=200005;
            while(L!=R){
                ll M=(L+R)/2;
                ll h=abs(q(M).first.first)+abs(q(M).second.first);
                if(h<=dis){
                    L=M+1;
                }else{
                    R=M;
                }
            }
            pair<ll,ll> u=q(L).first,v=q(L).second;
            if(u.second<v.second){
                ans[i]+=u.first;
                ans[i+1]+=dis-u.first;
            }else{
                ans[i+1]+=abs(v.first);
                ans[i]+=dis-abs(v.first);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

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