結果

問題 No.2791 Beginner Contest
ユーザー nouka28nouka28
提出日時 2024-06-21 22:30:54
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 19 ms
6,816 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 38 ms
9,344 KB
testcase_07 AC 8 ms
6,940 KB
testcase_08 AC 8 ms
6,940 KB
testcase_09 AC 52 ms
11,648 KB
testcase_10 AC 54 ms
11,904 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 65 ms
12,800 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include<atcoder/all>
using namespace atcoder;

#define int long long
const 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;
}
0