#1149239 (C++23) No.2808 Concentration

• 問題: No.2808 Concentration
• ユーザー: highlighter
• 提出日時: 2026-02-25 10:12:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 423 ms / 2,000 ms
• コード長: 3,438 bytes
• コンパイル時間: 4,294 ms
• コンパイル使用メモリ: 338,816 KB
• 実行使用メモリ: 17,476 KB
• 最終ジャッジ日時: 2026-02-25 10:13:14
• 合計ジャッジ時間: 27,298 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 57

ソースコード

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

template<class S,auto op,auto e>
struct segtree{
	private:
	int N;
	vector<S> val;
	public:
	segtree(int siz) : N(siz),val((siz<<1)-1,e()){}
	segtree(vector<S> A){
		N=(int)(A.size());
		val.resize((N<<1)-1);
		for(int i=N;i<(N<<1);i++){
			val[i-1]=A[i-N];
		}
		for(int i=N-1;i>0;i--){
			val[i-1]=op(val[(i<<1)-1],val[i<<1]);
		}
	}
	S get(int p){
		return val[p+N-1];
	}
	void set(int p,S x){
		p+=N;
		val[p-1]=x;
		while(p>1){
			p>>=1;
			val[p-1]=op(val[(p<<1)-1],val[p<<1]);
		}
	}
	S prod(int l,int r){
		l+=N,r+=N;
		S lret=e(),rret=e();
		for(;l<r;l>>=1,r>>=1){
			if(l&1){
				lret=op(lret,val[l-1]);
				l++;
			}
			if(r&1){
				r--;
				rret=op(val[r-1],rret);
			}
		}
		return op(lret,rret);
	}
	S all_prod(){
		return prod(0,N);
	}
};

template<class S,auto op,auto e,class F,auto mapping,auto composition,auto id>
struct lazy_segtree{
	private:
	int N;
	vector<S> val;
	vector<F> lazy;
	void eval(int p){
		int h=bit_width((unsigned int)p)-1;
		for(int i=h;i>0;i--){
			int node=(p>>i);
			val[node-1]=mapping(lazy[node-1],val[node-1]);
			lazy[(node<<1)-1]=composition(lazy[node-1],lazy[(node<<1)-1]);
			lazy[node<<1]=composition(lazy[node-1],lazy[node<<1]);
			lazy[node-1]=id();
		}
	}
	public:
	lazy_segtree(int siz) : N(siz),val((siz<<1)-1,e()),lazy((siz<<1)-1,id()){}
	lazy_segtree(vector<S> A){
		N=(int)(A.size());
		val.resize((N<<1)-1);
		lazy.assign((N<<1)-1,id());
		for(int i=N;i<(N<<1);i++){
			val[i-1]=A[i-N];
		}
		for(int i=N-1;i>0;i--){
			val[i-1]=op(val[(i<<1)-1],val[i<<1]);
		}
	}
	S get(int p){
		p+=N;
		eval(p);
		return mapping(lazy[p-1],val[p-1]);
	}
	void set(int p,S x){
		p+=N;
		eval(p);
		val[p-1]=x;
		lazy[p-1]=id();
		while(p>1){
			p>>=1;
			val[p-1]=op(mapping(lazy[(p<<1)-1],val[(p<<1)-1]),mapping(lazy[p<<1],val[p<<1]));
		}
	}
	S prod(int l,int r){
		l+=N,r+=N;
		S lret=e(),rret=e();
		int l0=l/(l&-l),r0=r/(r&-r);
		eval(l0),eval(r0);
		for(;l<r;l>>=1,r>>=1){
			if(l&1){
				lret=op(lret,mapping(lazy[l-1],val[l-1]));
				l++;
			}
			if(r&1){
				r--;
				rret=op(mapping(lazy[r-1],val[r-1]),rret);
			}
		}
		return op(lret,rret);
	}
	void apply(int l,int r,F x){
		l+=N,r+=N;
		int l0=l/(l&-l),r0=r/(r&-r);
		eval(l0),eval(r0);
		for(;l<r;l>>=1,r>>=1){
			if(l&1){
				lazy[l-1]=composition(x,lazy[l-1]);
				l++;
			}
			if(r&1){
				r--;
				lazy[r-1]=composition(x,lazy[r-1]);
			}
		}
		while(l0>1){
			l0>>=1;
			val[l0-1]=op(mapping(lazy[(l0<<1)-1],val[(l0<<1)-1]),mapping(lazy[l0<<1],val[l0<<1]));
		}
		while(r0>1){
			r0>>=1;
			val[r0-1]=op(mapping(lazy[(r0<<1)-1],val[(r0<<1)-1]),mapping(lazy[r0<<1],val[r0<<1]));
		}
	}
};

long long op(long long a,long long b){
	return max(a,b);
}
long long e(){
	return 0LL;
}
long long mapping(long long f,long long x){
	return f+x;
}
long long composition(long long f,long long g){
	return f+g;
}
long long id(){
	return 0;
}

int main(){
	int N;
	long long S,H;
	cin >> N >> S >> H;
	long long X[N];
	long long Y[N];
	long long Z[N];
	for(int i=0;i<N;i++){
		cin >> X[i] >> Y[i] >> Z[i];
	}
	lazy_segtree<long long,op,e,long long,mapping,composition,id> dpx(N);
	segtree<long long,op,e> dpy(N);
	dpx.set(0,Z[0]);
	if(Y[0]-X[0]<=S){
		dpy.set(0,Z[0]);
	}
	for(int i=1;i<N;i++){
		int r=upper_bound(Y,Y+i,X[i]-H)-Y;
		dpx.set(i,dpy.prod(0,r));
		dpx.apply(0,i+1,Z[i]);
		int l=lower_bound(X,X+i+1,Y[i]-S)-X;
		dpy.set(i,dpx.prod(l,i+1));
	}
	cout << dpy.all_prod() << endl;
}