Submission #34417853

---

Source Code Expand

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

template<typename ...Ts>
decltype(auto) zip(vector<Ts>... args){
  vector<decltype(make_tuple(args[0]...))> res;
  Int n=min({args.size()...});
  res.reserve(n);
  for(Int i=0;i<n;i++) res.emplace_back(args[i]...);
  return res;
}

template <typename T_, typename F_>
struct SegmentTree{
  using T = T_;
  using F = F_;
  Int n;
  F f;
  T ti;
  vector<T> dat;

  SegmentTree(F f,T ti):f(f),ti(ti){}

  void init(Int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }

  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(Int a,Int b){
    if(a>=b) return ti;
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  Int max_right(Int s,C &check,T &acc,Int k,Int l,Int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?-1:k-n;
    }
    Int m=(l+r)>>1;
    if(m<=s) return max_right(s,check,acc,(k<<1)|1,m,r);
    if(s<=l and check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    Int vl=max_right(s,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return max_right(s,check,acc,(k<<1)|1,m,r);
  }

  // max t s.t. check(query(s,t))
  // O(\log N)
  template<typename C>
  Int max_right(Int s,C &check){
    assert(s<n and check(ti) and not check(query(s,n)));
    T acc=ti;
    return max_right(s,check,acc,1,0,n);
  }
};

template<typename SegmentTree>
struct SegmentTree2D{
  using T = typename SegmentTree::T;
  using F = typename SegmentTree::F;
  const F f;
  const T ti;
  SegmentTree2D(F f_,T ti_):f(f_),ti(ti_){}

  vector<pair<Int, Int>> vp;
  void preupdate(Int p,Int q){
    vp.emplace_back(p,q);
  }

  void compress(vector<Int> &vs){
    sort(vs.begin(),vs.end());
    vs.erase(unique(vs.begin(),vs.end()),vs.end());
  }

  Int idx(Int v,const vector<Int> &vs){
    return lower_bound(vs.begin(),vs.end(),v)-vs.begin();
  }

  Int sz;
  vector<Int> ps;
  vector<vector<Int>> I,L,R;
  vector<SegmentTree> seg;
  void build(){
    for(auto[p,q]:vp) ps.emplace_back(p);
    compress(ps);

    sz=1;
    while(sz<(Int)ps.size()) sz<<=1;

    I.resize(sz<<1);
    for(auto[p,q]:vp) I[sz+idx(p,ps)].emplace_back(q);
    for(Int k=(Int)I.size()-1;k>=sz;k--) compress(I[k]);

    L.resize(sz);
    R.resize(sz);
    for(Int k=sz-1;k>0;k--){
      auto& cur=I[k];
      const auto& lft=I[(k<<1)|0];
      const auto& rgh=I[(k<<1)|1];
      cur.resize(lft.size()+rgh.size());
      merge(lft.begin(),lft.end(),rgh.begin(),rgh.end(),cur.begin());
      cur.erase(unique(cur.begin(),cur.end()),cur.end());
      L[k].resize(cur.size()+1);
      R[k].resize(cur.size()+1);
      Int tl=0,tr=0;
      for(Int i=0;i<(Int)cur.size();i++){
        while(tl<(Int)lft.size() and lft[tl]<cur[i]) tl++;
        while(tr<(Int)rgh.size() and rgh[tr]<cur[i]) tr++;
        L[k][i]=tl;R[k][i]=tr;
      }
      L[k][cur.size()]=lft.size();
      R[k][cur.size()]=rgh.size();
    }
    for(Int k=0;k<(Int)I.size();k++){
      seg.emplace_back(f,ti);
      seg.back().build(vector<T>(I[k].size(),ti));
    }
  }

  void update(Int p,Int q,T v,Int k,Int l,Int r){
    if(r<=p||p+1<=l) return;
    if(p<=l&&r<=p+1) return seg[k].set_val(q,v);
    Int m=(l+r)>>1;
    update(p,L[k][q],v,(k<<1)|0,l,m);
    update(p,R[k][q],v,(k<<1)|1,m,r);
    T res=ti;
    const auto& cur=I[k];
    const auto& lft=I[(k<<1)|0];
    const auto& rgh=I[(k<<1)|1];
    if(L[k][q]<(Int)lft.size() and cur[q]==lft[L[k][q]])
      res=f(res,seg[(k<<1)|0].query(L[k][q],L[k][q]+1));
    if(R[k][q]<(Int)rgh.size() and cur[q]==rgh[R[k][q]])
      res=f(res,seg[(k<<1)|1].query(R[k][q],R[k][q]+1));
    seg[k].set_val(q,res);
  }

  void update(Int p,Int q,T v){
    update(idx(p,ps),idx(q,I[1]),v,1,0,sz);
  }

  T query(Int pa,Int pb,Int qa,Int qb,Int k,Int l,Int r){
    if(r<=pa||pb<=l) return ti;
    if(pa<=l&&r<=pb) return seg[k].query(qa,qb);
    Int m=(l+r)>>1;
    return f(query(pa,pb,L[k][qa],L[k][qb],(k<<1)|0,l,m),
             query(pa,pb,R[k][qa],R[k][qb],(k<<1)|1,m,r));
  }

  // [pa, pb) x [qa, qb)
  T query(Int pa,Int pb,Int qa,Int qb){
    return query(idx(pa,ps),idx(pb,ps),idx(qa,I[1]),idx(qb,I[1]),1,0,sz);
  }
};

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;
  vector<Int> ts(n),xs(n),ys(n),as(n);
  for(Int i=0;i<n;i++) cin>>ts[i]>>xs[i]>>ys[i]>>as[i];

  {
    auto zs=zip(ys,ts,xs,as);
    sort(zs.begin(),zs.end());
    for(Int i=0;i<n;i++) tie(ys[i],ts[i],xs[i],as[i])=zs[i];
  }
  vector<Int> bs(n),cs(n);
  for(Int i=0;i<n;i++){
    bs[i]=ts[i]-ys[i]+xs[i];
    cs[i]=ts[i]-ys[i]-xs[i];
  }
  // i->j <=> v[i]<=v[j] for all (ts,ys,bs,cs)

  auto f=[&](Int a,Int b){return max(a,b);};
  SegmentTree2D<SegmentTree<Int, decltype(f)>> seg(f,0);
  for(Int i=0;i<n;i++){
    seg.preupdate(bs[i],cs[i]);
  }
  seg.build();

  Int ans=0;
  for(Int i=0;i<n;i++){
    if(ts[i]<xs[i]+ys[i]) continue;
    Int res=as[i]+seg.query(0,bs[i]+1,0,cs[i]+1);
    seg.update(bs[i],cs[i],res);
    chmax(ans,res);
  }
  cout<<ans<<newl;

  return 0;
}

Submission Info

Judge Result