Submission #66901926

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int m=1e5;
typedef long long ll;
int n; ll c,d;
ll a[N]; 
ll sum;

struct segtree{
    #define maxx N*4
    #define ls x<<1
    #define rs x<<1|1
    ll mn[maxx],mx[maxx],add[maxx],cov[maxx];
    ll sum[maxx]; int len[maxx];
    void push_up(int x) {
        mn[x]=min(mn[ls],mn[rs]);
        mx[x]=max(mx[ls],mx[rs]);
        sum[x]=sum[ls]+sum[rs];
    }
    void build(int x,int l,int r) {
        len[x]=r-l+1;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(ls,l,mid); build(rs,mid+1,r);
    }
    void cover(int x,ll w) {
        add[x]=0; cov[x]=w;
        mn[x]=mx[x]=w;
        sum[x]=1ll*len[x]*w;
    }
    void adding(int x,ll w) {
        add[x]+=w; 
        mn[x]+=w; mx[x]+=w;
        sum[x]+=1ll*len[x]*w;
    }
    void push_down(int x) {
        if(cov[x]) {
            cover(ls,cov[x]);
            cover(rs,cov[x]);
            cov[x]=0; 
        }
        if(add[x]) {
            adding(ls,add[x]);
            adding(rs,add[x]);
            add[x]=0;
        }
    }
    void updateAdd(int x,int l,int r,int a,int b,ll w) {
        if(l>=a&&r<=b) {
            adding(x,w);
            return;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if(mid>=a) updateAdd(ls,l,mid,a,b,w);
        if(mid+1<=b) updateAdd(rs,mid+1,r,a,b,w);
        push_up(x);
    }
    void updateCover(int x,int l,int r,int a,int b,ll w) {
        if(l>=a&&r<=b) {
            cover(x,w);
            return;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if(mid>=a) updateCover(ls,l,mid,a,b,w);
        if(mid+1<=b) updateCover(rs,mid+1,r,a,b,w);
        push_up(x);
    }
    int queryMin(int x,int l,int r,ll w) {
        if(l==r) {
            if(mn[x]>=w) return l;
            return m+1;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if(mx[ls]>=w) return queryMin(ls,l,mid,w);
        else return queryMin(rs,mid+1,r,w);
    }
    int queryMax(int x,int l,int r,ll w) {
        if(l==r) {
            if(mx[x]<=w) return l;
            return -m;
        }
        push_down(x);
        int mid=(l+r)>>1;
        if(mn[rs]<=w) return queryMax(rs,mid+1,r,w);
        else return queryMax(ls,l,mid,w);
    }
    ll query(int x,int l,int r,int a) {
        if(l==r) return mx[x];
        push_down(x);
        int mid=(l+r)>>1;
        if(mid>=a) return query(ls,l,mid,a);
        else return query(rs,mid+1,r,a);
    }
    ll querySum(int x,int l,int r,int a,int b) {
        if(l>=a&&r<=b) return sum[x];
        push_down(x);
        int mid=(l+r)>>1;
        ll ans=0;
        if(mid>=a) ans+=querySum(ls,l,mid,a,b);
        if(mid+1<=b) ans+=querySum(rs,mid+1,r,a,b);
        return ans;
    }
}t;
int lpos[N],rpos[N];

void debugger() {
    printf("--%lld\n",sum);
    for(int i=-m+1;i<=m;i++) printf("%lld ", t.query(1,-m,m,i));
    puts("");
}
int ans[N];
int main() {
    t.build(1,-m,m);
    scanf("%d%lld%lld",&n,&c,&d);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll pos=-m;
    sum=-pos*c;
    t.updateCover(1,-m,m,-m,0,-c);
    t.updateCover(1,-m,m,1,m,c);
   // debugger();
    for(int i=1;i<=n;i++) {
        sum+=abs(pos-a[i])*d;
        //debugger();
        int lc=t.queryMax(1,-m,m,-c);
        int rc=t.queryMin(1,-m,m,c);
        if(lc>-m) {
            ll sm=t.querySum(1,-m,m,-m+1,lc);
            sum-=(-sm-1ll*c*(m+lc));
            t.updateCover(1,-m,m,-m,lc,-c);
        }
        if(rc!=m+1) t.updateCover(1,-m,m,rc,m,c);
        lpos[i]=lc; rpos[i]=rc-1;
        t.updateAdd(1,-m,m,-m,a[i],-d);
        if(a[i]+1<=m) t.updateAdd(1,-m,m,a[i]+1,m,d);
        //debugger();
    }
    for(int i=-m+1;i<=m;i++) {
        ll w=t.query(1,-m,m,i);
        if(w<=0) sum+=w,pos=i;
        else break;
    }
    printf("%lld\n",sum);
    ans[n]=pos;
    for(int i=n;i>=2;i--) {
        pos=min(pos,(ll)rpos[i]);
        pos=max(pos,(ll)lpos[i]);
        ans[i-1]=pos;
    } 
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:118:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |     scanf("%d%lld%lld",&n,&c,&d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:119:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  119 |     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~~~

Judge Result