Submission #534215

#TimeUsernameProblemLanguageResultExecution timeMemory
534215BiazSnowball (JOI21_ho_t2)C++17
33 / 100
2575 ms4016 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define X first
#define Y second
#define ist insert
typedef long long ll;
//typedef pair<int,int> pii;
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
const int INF=1700000000000000;//2147483647;
const int MOD=998244353;//1000000007;
const int N=200005;
int n,Q;
int a[N],w[N],res[N];
int mxL[N],mxR[N];
void sol(){
    cin >>n>>Q;
    for (int i=1;i<=n;i++)
        cin >>a[i],mxL[i]=mxR[i]=a[i];
    a[0]=mxL[0]=mxR[0]=-INF;mxL[n+1]=mxR[n+1]=a[n+1]=INF;
    for (int i=1;i<=Q;i++)
        cin >>w[i];

    int cur=0;
    for (int xx=1;xx<=Q;xx++){
        cur+=w[xx];
        for (int i=1;i<=n;i++){
            if (mxL[i]<=a[i]+cur&&a[i]+cur<=mxR[i]) continue;
            if (cur>0) res[i]+=max(0,min(mxL[i+1],a[i]+cur)-mxR[i]);
            if (cur<0) res[i]+=max(0,mxL[i]-max((a[i]+cur),mxR[i-1]));
        }
        for (int i=1;i<=n;i++){
            mxL[i]=min(mxL[i],a[i]+cur);
            mxR[i]=max(mxR[i],a[i]+cur);
        }
        /*for (int i=1;i<=n;i++)
        cout <<res[i]<<' ';cout <<'\n';
        for (int i=1;i<=n;i++)
            cout <<mxL[i]<<' '<<mxR[i]<<'\n';*/
    }
    
    for (int i=1;i<=n;i++)
        cout <<res[i]<<'\n';
}
signed main()
{
    int _=1;
    //cin >>_;
    while (_--) sol();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...