結果
| 問題 | No.2791 Beginner Contest |
| ユーザー |
 nouka28
|
| 提出日時 | 2024-06-21 22:30:54 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 65 ms / 2,000 ms |
| コード長 | 5,547 bytes |
| コンパイル時間 | 4,831 ms |
| コンパイル使用メモリ | 311,664 KB |
| 実行使用メモリ | 12,800 KB |
| 最終ジャッジ日時 | 2024-06-21 22:31:01 |
| 合計ジャッジ時間 | 6,139 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;#define int long longconst long long inf=1LL<<62;using mint=atcoder::modint998244353;template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S,int),F (*composition)(F,F),F (*id)()>class dynamic_lazy_segtree{public:dynamic_lazy_segtree(int n):n(n){root=new node(e(),id(),n);}void set(int p,S x){assert(p<n);set(root,0,n,p,x);}S get(int p)const{assert(p<n);return get(root,0,n,p);}void apply(int l,int r,F f){assert(0<=l&&l<=r&&r<=n);apply(root,0,n,l,r,f);}S prod(int l,int r)const{assert(0<=l&&l<=r&&r<=n);return prod(root,0,n,l,r);}S all_prod()const{return prod(0,n);}template<bool (*f)(S)> int max_right(int l)const{return max_right(l,[](S x){return f(x);});}template<class G> int max_right(int l,const G& f)const{assert(l<=n);S product=e();assert(f(product));return max_right(root,0,n,l,f,product);}template<bool (*f)(S)> int min_left(int r)const{return min_left(r,[](S x){return f(x);});}template<class G> int min_left(int r,const G& f)const{assert(r<=n);S product=e();assert(f(product));return min_left(root,0,n,r,f,product);}void dump(){dump(root,0,n);cout<<endl;}private:struct node{S value;F lazy,lazy_acc;node *left,*right;node(S value=e(),F lazy=id(),int l=0):value(value),lazy(lazy),lazy_acc(id()),left(nullptr),right(nullptr){eval(l);}void update(int l,int r){int m=(l+r)>>1;value=op(left?left->value:mapping(lazy_acc,e(),m-l),right?right->value:mapping(lazy_acc,e(),r-m));return;}void eval(int l){value=mapping(lazy,value,l);if(left)left->lazy=composition(lazy,left->lazy);if(right)right->lazy=composition(lazy,right->lazy);lazy_acc=composition(lazy,lazy_acc);lazy=id();return;}};int n;node* root;void set(node* t,int l,int r,int p,S x)const{t->eval(r-l);int m=(l+r)>>1;if(l==p&&r==p+1){t->value=x;return;}else{if(!t->left)t->left=new node(e(),t->lazy_acc,m-l);if(!t->right)t->right=new node(e(),t->lazy_acc,r-m);}if(p<m){set(t->left,l,m,p,x);}else{set(t->right,m,r,p,x);}t->update(l,r);}S get(node* t,int l,int r,int p)const{t->eval(r-l);if(l==p&&r==p+1){return t->value;}int m=(l+r)>>1;if(p<m)return t->left?get(t->left,l,m,p):mapping(t->lazy_acc,e(),1);else return t->right?get(t->right,m,r,p):mapping(t->lazy_acc,e(),1);}void apply(node* t,int l,int r,int a,int b,F f)const{t->eval(r-l);if(b<=l||r<=a)return;if(a<=l&&r<=b){t->lazy=composition(f,t->lazy);t->eval(r-l);return;}int m=(l+r)>>1;if(!t->left){t->left=new node(e(),t->lazy_acc,m-l);}if(!t->right){t->right=new node(e(),t->lazy_acc,r-m);}apply(t->left,l,m,a,b,f);apply(t->right,m,r,a,b,f);t->update(l,r);}S prod(node* t,int l,int r,int a,int b)const{t->eval(r-l);if(b<=l||r<=a)return e();if(a<=l&&r<=b)return t->value;int m=(l+r)>>1;return op(t->left?prod(t->left,l,m,a,b):mapping(t->lazy_acc,e(),max(0LL,min(m,b)-max(l,a))),t->right?prod(t->right,m,r,a,b):mapping(t->lazy_acc,e(),max(0LL,min(r,b)-max(m,a))));}template<class G>int max_right(node* t,int l,int r,int L,const G& f,S &product)const{t->eval(r-l);if(r<=L)return r;if(!f(product))return l;if(f(op(product,prod(t,l,r,L,n))))return r;int m=(l+r)>>1;int res=t->left?max_right(t->left,l,m,L,f,product):m;if(res!=m)return res;product=op(product,t->left?prod(t->left,l,m,L,n):mapping(t->lazy_acc,e(),m-l));if(!f(product))return l;return t->right?max_right(t->right,m,r,L,f,product):r-1;}template<class G>int min_left(node* t,int l,int r,int R,const G& f,S &product)const{t->eval(r-l);if(l>=R)return l;if(!f(product))return r;if(f(op(product,prod(t,l,r,0,R))))return l;int m=(l+r)>>1;int res=t->right?min_left(t->right,m,r,R,f,product):m;if(res!=m)return res;product=op(product,t->right?prod(t->right,m,r,0,r):mapping(t->lazy_acc,e(),r-m));if(!f(product))return r;return t->left?min_left(t->left,l,m,R,f,product):l+1;}void dump(node* t,int l,int r){t->eval(r-l);cout<<"("<<l<<" "<<r<<" "<<t->value<<" "<<t->lazy_acc<<"),";int m=(l+r)>>1;if(t->left)dump(t->left,l,m);if(t->right)dump(t->right,m,r);}};mint op(mint a,mint b){return a+b;}mint e(){return 0;}mint mapping(mint f,mint x,int l){return x+f*l;}signed main(){int n,k;cin>>n>>k;dynamic_lazy_segtree<mint,op,e,mint,mapping,op,e> seg(n+1);seg.set(0,1);for(int i=0;i<n;i++){if(i+k<=n)seg.apply(i+k,n+1,seg.get(i));}cout<<seg.all_prod().val()<<endl;}