結果

問題 No.631 Noelちゃんと電車旅行
ユーザー beet
提出日時 2018-01-05 21:29:15
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 576 ms
コード長 2,251 Byte
コンパイル時間 1,284 ms
使用メモリ 9,320 KB
最終ジャッジ日時 2020-01-13 23:58:04

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
LEARGE_case1.txt AC 560 ms
9,156 KB
LEARGE_case2.txt AC 544 ms
9,132 KB
LEARGE_case3.txt AC 576 ms
9,320 KB
LEARGE_case4.txt AC 548 ms
9,316 KB
LEARGE_case5.txt AC 536 ms
9,168 KB
RANDOM_case1.txt AC 220 ms
5,892 KB
RANDOM_case2.txt AC 112 ms
6,324 KB
RANDOM_case3.txt AC 400 ms
8,960 KB
RANDOM_case4.txt AC 472 ms
6,000 KB
RANDOM_case5.txt AC 324 ms
8,792 KB
RANDOM_case6.txt AC 316 ms
6,340 KB
RANDOM_case7.txt AC 376 ms
8,968 KB
RANDOM_case8.txt AC 356 ms
4,444 KB
RANDOM_case9.txt AC 164 ms
3,504 KB
RANDOM_case10.txt AC 304 ms
4,644 KB
SMALL_case1.txt AC 4 ms
3,236 KB
SMALL_case2.txt AC 0 ms
3,256 KB
SMALL_case3.txt AC 4 ms
3,396 KB
SMALL_case4.txt AC 4 ms
3,232 KB
SMALL_case5.txt AC 0 ms
3,304 KB
テストケース一括ダウンロード

ソースコード

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

template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  typedef function<E(E,E)> H;
  typedef function<E(E,Int)> P;
  Int n;
  F f;
  G g;
  H h;
  P p;
  T d1;
  E d0;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(Int n_,F f,G g,H h,T d1,E d0,
	      vector<T> v=vector<T>(),P p=[](E a,Int b){return a;}):
    f(f),g(g),h(h),d1(d1),d0(d0),p(p){
    init(n_);
    if(n_==(Int)v.size()) build(n_,v);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
    laz.clear();
    laz.resize(2*n-1,d0);
  }
  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]==d0) 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]=d0;
  }
  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 d1;
    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]);
    }
  }
};


signed main(){
  Int n;
  cin>>n;n--;
  vector<Int> v(n);
  for(Int i=0;i<n;i++) cin>>v[i];
  for(Int i=0;i<n;i++) v[i]-=3*i;
  auto f=[](Int a,Int b){return max(a,b);};
  auto g=[](Int a,Int b){return a+b;};
  SegmentTree<Int, Int> seg(n,f,g,g,0,0,v);
  Int m;
  cin>>m;
  for(Int i=0;i<m;i++){
    Int l,r,x;
    cin>>l>>r>>x;
    l--;
    seg.update(l,r,x);
    cout<<seg.query(0,n)+n*3<<endl;
  }
  return 0;
}
0