Submission #516710

#	Time	Username	Problem	Language	Result	Execution time	Memory
516710		jk410	Snowball (JOI21_ho_t2)	C++17	100 / 100	111 ms	18544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct state{
    ll p,n,cur;
};
int N,Q;
ll X[200001],W[200001],Sum[200001],Ans[200001];
state A[200001];
void debug(){
    for (int i=1; i<=Q; i++)
        cout<<Sum[i]<<" ";
    cout<<"\n\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.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];
        A[i]=A[i-1];
        A[i].cur+=W[i];
        if (A[i].cur>0)
            A[i].p=max(A[i].p,A[i].cur);
        else
            A[i].n=max(A[i].n,-A[i].cur);
        Sum[i]=A[i].p+A[i].n;
    }
    for (int i=1; i<N; i++){
        ll len=X[i+1]-X[i];
        int t=lower_bound(Sum+1,Sum+Q+1,len)-Sum;
        if (t>Q){
            Ans[i]+=A[Q].p;
            Ans[i+1]+=A[Q].n;
        }
        else{
            if (A[t].p==A[t-1].p){
                Ans[i]+=A[t].p;
                Ans[i+1]+=len-A[t].p;
            }
            else{
                Ans[i+1]+=A[t].n;
                Ans[i]+=len-A[t].n;
            }
        }
    }
    Ans[1]+=A[Q].n;
    Ans[N]+=A[Q].p;
    for (int i=1; i<=N; i++)
        cout<<Ans[i]<<"\n";
    return 0;
}

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