Submission #706146

#	Time	Username	Problem	Language	Result	Execution time	Memory
706146		pcc	Snowball (JOI21_ho_t2)	C++14	100 / 100	100 ms	11956 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const ll mxn = 2e5+10;
const ll inf = 1e18;
ll arr[mxn];
ll req[mxn];
pll maxi[mxn];
bool isl[mxn];
ll ans[mxn];
ll n,q;

ll calc(ll len){
    ll l = 0,r = q;
    while(l != r){
        ll mid = (l+r+1)>>1;
        if(maxi[mid].sc-maxi[mid].fs>len)r = mid-1;
        else l = mid;
    }
    if(r >= q)return q;
    else return l;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    arr[0] = -inf,arr[n+1] = inf;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    ll now = 0;
    for(int i = 1;i<=q;i++){
        cin>>req[i];
        if(req[i]==0){
            q--;
            i--;
            continue;
        }
        maxi[i] = maxi[i-1];
        now += req[i];
        if(maxi[i].fs>now)isl[i] = true;
        if(maxi[i].sc<now)isl[i] = false;
        maxi[i].fs = min(maxi[i].fs,now);
        maxi[i].sc = max(maxi[i].sc,now);
    }
    for(int i = 1;i<=n+1;i++){
        auto re = calc(arr[i]-arr[i-1]);
        ans[i-1] += maxi[re].sc;
        ans[i] -= maxi[re].fs;
        if(re != q&&!isl[re+1])ans[i-1] += (arr[i]-arr[i-1])-(maxi[re].sc-maxi[re].fs);
        else if(re != q&&isl[re+1])ans[i] += (arr[i]-arr[i-1])-(maxi[re].sc-maxi[re].fs);
    }
    for(int i = 1;i<=n;i++)cout<<ans[i]<<'\n';
}

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