Submission #10631351

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

template<class T> struct STree{
    int n;
    T e;
    vector<T> dat;

    inline T f(T x,T y){
        return max(x,y);
    }

    STree(int n_,T e_){
        n=1;e=e_;
        while(n<n_) n<<=1;
        dat.resize((n<<1),e);
    }

    STree(vector<T> v,T e_){
        int n_=v.size();
        n=1;e=e_;
        while(n<n_) n<<=1;
        dat.resize((n<<1),e);
        for(int i=0;i<n_;++i) dat[i+n]=v[i];
        for(int i=n-1;i>0;--i) dat[i]=f(dat[(i<<1)],dat[(i<<1)^1]);
    }

    void ud(int k,T c){
        k+=n;
        dat[k]=c;
        while(k){
            dat[k>>1]=f(dat[k],dat[k^1]);
            k>>=1;
        }
    }

    T gt(int l,int r){
        l+=n;r+=n;
        T s=e;
        while(l<r){
            if(r&1){
                --r;
                s=f(s,dat[r]);
            }
            if(l&1){
                s=f(s,dat[l]);
                ++l;
            }
            l>>=1,r>>=1;
        }
        return s;
    }

    T operator[](int i){return dat[i+n];}
};

struct modint{
    using i64=int_fast64_t;
    i64 a;
    static constexpr i64 MOD=998244353;
    modint(){a=0;}
    modint(i64 a_){
        a=a_%MOD;
        if(a<0) a+=MOD;
    }
    modint inv()const{
        i64 n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y;
        y.a=n;
        return y;
    }
    bool operator==(const modint& x){
        return a==x.a;
    }
    bool operator!=(const modint& x){
        return a!=x.a;
    }
    modint& operator=(const modint& x){
        a=x.a;
        return *this;
    }
    modint operator+(const modint& x){
        modint y;
        y.a=a+x.a;
        if(y.a>MOD) y.a-=MOD;
        return y;
    }
    modint operator-(const modint& x){
        modint y;
        y.a=a-x.a;
        if(y.a<0) y.a+=MOD;
        return y;
    }
    modint operator*(const modint& x){
        modint y;
        y.a=(a*x.a)%MOD;
        return y;
    }
    modint operator/(const modint& x){
        modint y;
        y.a=(a*x.inv().a)%MOD;
        return y;
    }
    modint& operator+=(const modint& x){
        a+=x.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    modint& operator-=(const modint& x){
        a-=x.a;
        if(a<0) a+=MOD;
        return *this;
    }
    modint& operator*=(const modint& x){
        (a*=x.a)%=MOD;
        return *this;
    }
    modint& operator/=(const modint& x){
        (a*=x.inv().a)%=MOD;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x){
    int_fast64_t a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x){
    out<<x.a;
    return out;
}
modint pwr(int_fast64_t a,int_fast64_t b){
    modint _;
    int_fast64_t n=1,A=a;
    while(b){
        if(b&1) (n*=A)%=modint::MOD;
        (A*=A)%=modint::MOD;
        b>>=1;
    }
    _.a=n;
    return _;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n;
    in>>n;
    vector<pair<int,int>> xd(n);
    for(auto&p:xd) in>>p.first>>p.second;
    sort(xd.begin(),xd.end());
    vector<int> x(n),d(n);
    fr(i,n) tie(x[i],d[i])=xd[i];
    vector<modint> dp(n+1);
    dp[n]=1;
    STree<int> st(n,-1);
    fr(i,n) st.ud(i,i+1);
    ifr(i,n){
        dp[i]=dp[i+1];
        int j=lower_bound(x.begin(),x.end(),x[i]+d[i])-x.begin();
        j=st.gt(i,j);
        st.ud(i,j);
        dp[i]+=dp[j];
    }
    cout<<dp[0]<<endl;
    
}

Submission Info

Judge Result