結果

問題 No.2808 Concentration
コンテスト
ユーザー highlighter
提出日時 2026-02-25 10:27:32
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 456 ms / 2,000 ms
コード長 3,476 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,890 ms
コンパイル使用メモリ 343,228 KB
実行使用メモリ 17,512 KB
最終ジャッジ日時 2026-02-25 10:27:57
合計ジャッジ時間 23,989 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;

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]);
		}
	}
	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 get(int p){
		p+=N;
		eval(p);
		return 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]));
		}
	}
};

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());
		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]);
		}
	}
	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 get(int p){
		return val[p+N-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);
	}
};

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;
}
0