Submission #2822090

---

Source Code Expand

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


struct EulerTour{
  Int n,pos;
  vector<vector<Int> > G;
  vector<Int> ls,rs;
  
  EulerTour(){}
  EulerTour(Int n):n(n),G(n),ls(n),rs(n){}

  void add_edge(Int u,Int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(Int v,Int p){
    ls[v]=pos++;
    for(Int u:G[v])
      if(u!=p) dfs(u,v);
    rs[v]=pos;
  }
  
  void build(Int r=0){
    pos=0;
    dfs(r,-1);
  }
  
};


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using P = function<E(E,size_t)>;
  Int n;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  P p;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(Int n_,F f,G g,H h,T ti,E ei,
	      P p=[](E a,size_t b){b++;return a;}):
    f(f),g(g),h(h),ti(ti),ei(ei),p(p){
    init(n_);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
    laz.assign(2*n-1,ei);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  inline void eval(Int len,Int k){
    if(laz[k]==ei) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1],laz[k]);
      laz[k*2+2]=h(laz[k*2+2],laz[k]);
    }
    dat[k]=g(dat[k],p(laz[k],len));
    laz[k]=ei;
  }
  T update(Int a,Int b,E x,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k]=h(laz[k],x);
      return g(dat[k],p(laz[k],r-l));
    }
    return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
		    update(a,b,x,k*2+2,(l+r)/2,r));
  }
  T update(Int a,Int b,E x){
    return update(a,b,x,0,0,n);
  }
  T query(Int a,Int b,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return ti;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(Int a,Int b){
    return query(a,b,0,0,n);
  }
  void update(Int k,T x){
    query(k,k+1);//evaluate
    k+=n-1;
    dat[k]=x;
    while(k){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<string> a(n);
  vector<Int> b(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i];

  vector<vector<Int> > G(1);
  vector<map<char, Int> > M(1);
  for(Int i=0;i<n;i++){
    reverse(a[i].begin(),a[i].end());
    Int pos=0;
    for(Int j=0;j<(Int)a[i].size();j++){
      if(!M[pos].count(a[i][j])){
	M[pos][a[i][j]]=G.size();
	G[pos].emplace_back(M[pos][a[i][j]]);
	G.emplace_back();
	M.emplace_back();
      }
      pos=M[pos][a[i][j]];
    }
  }

  EulerTour et(G.size());
  for(Int i=0;i<(Int)G.size();i++)
    for(Int u:G[i]) et.add_edge(i,u);
  et.build();

  auto f=[](Int a,Int b){return max(a,b);};
  auto g=[](Int a,Int b){return a+b;};
  SegmentTree<Int, Int> seg(G.size(),f,g,g,0,0);
  
  for(Int i=0;i<n;i++){
    Int pos=0;
    for(Int j=0;j<(Int)a[i].size();j++)
      pos=M[pos][a[i][j]];

    seg.update(et.ls[pos],et.rs[pos],b[i]);
    cout<<seg.query(0,G.size())<<endl;
  }
  
  return 0;
}

Submission Info

Judge Result