Submission #1437110

---

Source Code Expand

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

struct BIT{
  vector<int> bit;
  int n;
  //1-indexed
  BIT(){init(-1);}
  BIT(int n_){init(n_);}
  void init(int n_){
    n=n_;
    bit.clear();
    bit.resize(n+1,0);
  }
  int sum(int i){
    int s=0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }
  void add(int i,int x){
    if(i==0) return;
    while(i<=n){
      bit[i]+=x;
      i+=i&-i;
    }
  }
  int sum0(int i){
    return sum(i+1);
  }
  void add0(int i,int x){
    add(i+1,x);
  }
};

struct StarrySky{
  int n;
  const int def=1LL<<55LL;
  vector<int> datm,data;
  StarrySky(){}
  StarrySky(int n_){init(n_);}
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    datm.clear();
    datm.resize(n*2-1,def);
    data.clear();
    data.resize(n*2-1,0);
  }
  void add(int a,int b,int x,int k,int l,int r){
    if(r<=a||b<=l) return;
    if(a<=l&&r<=b){
      data[k]+=x;
      return;
    }
    add(a,b,x,k*2+1,l,(l+r)/2);
    add(a,b,x,k*2+2,(l+r)/2,r);
    datm[k]=min(datm[k*2+1]+data[k*2+1],
		datm[k*2+2]+data[k*2+2]);
  }
  int query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return def;
    if(a<=l&&r<=b) return datm[k]+data[k];
    int vl=query(a,b,k*2+1,l,(l+r)/2);
    int vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr)+data[k];
  }
  void add(int a,int b,int x){
    add(a,b,x,0,0,n);
  }
  int query(int a,int b){
    return query(a,b,0,0,n);
  }
};

signed main(){
  int n,e,t;
  cin>>n>>e>>t;
  int x[n+1];
  for(int i=0;i<n;i++) cin>>x[i];
  x[n]=e;
  
  int dp[n+1];
  int INF=1LL<<55LL;
  fill_n(dp,n+1,INF);
  dp[0]=x[0];

  BIT bit(n+1);
  StarrySky ss(n+1);
  
  for(int i=0;i<n;i++){
    bit.add0(i,-x[i]*2);
    bit.add0(i+1,x[i]*2);
  }
  ss.add(0,1,t-ss.def);
  int k=0,pre=0;
  for(int j=0;j<n;j++){
    bit.add0(0,2*(x[j]-pre));
    ss.add(0,k,2*(x[j]-pre));
    pre=x[j];
    while(k<=j&&bit.sum0(k)>=t){
      ss.add(k,k+1,bit.sum0(k)-t);
      k++;
    }
    /*
    cout<<"bit"<<endl;
    for(int i=0;i<=n;i++)
      cout<<i<<":"<<bit.sum0(i)<<endl;
    cout<<endl;
    cout<<"ss"<<endl;
    for(int i=0;i<=n;i++)
      cout<<i<<":"<<ss.query(i,i+1)<<endl;
    cout<<endl;
    */
    
    int res=ss.query(0,j+1);
    dp[j+1]=res+x[j+1];
    ss.add(j+1,j+2,(res+t)-ss.query(j+1,j+2));
    /*
    cout<<"k:"<<k<<endl;
    cout<<"res:"<<res<<endl;
    cout<<"dp[j+1]:"<<dp[j+1]<<endl;
    cout<<j<<":"<<res<<endl;
    cout<<"----------"<<endl;
    */
  }
  cout<<dp[n]<<endl;
  return 0;
}

Submission Info

Judge Result