Language: C++

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const ll MOD = 998244353;

int B = 450;
// バケット i は [i*B, (i+1)*B) の記録を持つ
// lazy[i] :=  バケットi の遅延を記録する
// 遅延が-1 ... 制約よりそんなことは発生しないことを利用して, これを遅延の単位元とできる
// i.e. lazy[i] == -1 def 消化時に何も伝播させないという遅延を与えるとみなす
// mi[i] := パケットi の最小値
vll lazy(B, -1), mi(B, (1LL << 31) - 1), a(2e5 + 10);

// a_s, ..., a_t を x に変更する
void update(int s, int t, int x)
{
    // s の属するバケット, t の属するバケット
    int st = s / B, gt = t / B;

    // st や gt に遅延が存在するとき更新前に消化しておく
    // 遅延はパケットごとに考えるから, 遅延が存在⇔パケット内は全て等しい値で更新されている
    // したがって mi[st] = lazy[st] が成立
    // 区間に被覆されるパケットについてはこのあと新しい値へ更新されるので消化しなくてOK
    if (lazy[st] != -1){
        for (int i = st * B; i < (st + 1) * B; i++) a[i] = lazy[st];
        mi[st] = lazy[st];
        lazy[st] = -1;
    }
    if (lazy[gt] != -1){
        for (int i = gt * B; i < (gt + 1) * B; i++) a[i] = lazy[gt];
        mi[gt] = lazy[gt];
        lazy[gt] = -1;
    }
    //... || ... s ... t ... || ...
    //更新が同一パケット内で済むなら直接更新しても間に合う
    if (st == gt){
        for (int i = s; i <= t; i++) a[i] = x;
        mi[st] = INT_MAX;
        for (int i = st * B; i < (st + 1) * B; i++) mi[st] = min(mi[st], a[i]);
    }

    //... s ... || (被覆されるパケット) || ... t ...
    //a の更新に伴う mi の更新が区間が属する全てのパケットに対し行われていることが重要
    else{
        //端が属するパケット内は直接更新
        for (int i = s; i < (st + 1) * B; i++) a[i] = x;
        mi[st] = INT_MAX;
        for (int i = st * B; i < (st + 1) * B; i++) mi[st] = min(mi[st], a[i]);
 
        for (int i = gt * B; i <= t; i++) a[i] = x;
        mi[gt] = INT_MAX;
        for (int i = gt * B; i < (gt + 1) * B; i++) mi[gt] = min(mi[gt], a[i]);

        //区間に被覆されるパケットについては更新を遅延に残す
        //区間内すべて更新されるのでパケットの最小値は x になる
        for (int i = st + 1; i < gt; i++){
            lazy[i] = x;
            mi[i] = x;
        }
    }
}

int find(int s, int t)
{
    int ret = INT_MAX;
    int st = s / B, gt = t / B;

    // st や gt に遅延が存在するとき
    // update() と同様に遅延を先に処理する
    if (lazy[st] != -1){
        for (int i = st * B; i < (st + 1) * B; i++) a[i] = lazy[st];
        mi[st] = lazy[st];
        lazy[st] = -1;
    }
    if (lazy[gt] != -1){
        for (int i = gt * B; i < (gt + 1) * B; i++) a[i] = lazy[gt];
        mi[gt] = lazy[gt];
        lazy[gt] = -1;
    }

    //... || ... s ... t ... || ...
    //直接計算
    if (st == gt){
        for (int i = s; i <= t; i++) ret = min(ret, a[i]);
    }
    //... s ... || (被覆されるパケット)  || ... t ...
    else{
        //端が属するパケット内は直接更新
        for (int i = s; i < (st + 1) * B; i++) ret = min(ret, a[i]);
        for (int i = gt * B; i <= t; i++) ret = min(ret, a[i]);

        //被覆されるパケットはパケット単位で調査する
        for (int i = st + 1; i < gt; i++){
            //遅延が存在しない場合, update() によって mi[i] に最小値が保持されている
            if (lazy[i] == -1) ret = min(ret, mi[i]);
            //遅延が存在するならばパケット内は全て等しい値 lazy[i] になっている
            else ret = min(ret, lazy[i]);
        }
    }
    return ret;
}

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    ll x, l;
    vector<P> p(n);
    vll pos(n);
    REP(i, n) {
        cin >> x >> l;
        p[i] = {x, l};
        pos[i] = x;
    }
    VSORT(p);
    VSORT(pos);
    vll mem(n + 1);
    mem[n] = 1;
    REP(i, n) {
        a[i] = -(p[i].first + p[i].second);
    }
    vll right(n + 1);
    right[n] = n;
    REPR(i, n) {
        ll lb = lower_bound(ALL(pos), p[i].first + p[i].second) - pos.begin(); // 直接届かない最小の位置
        ll ub = lb - 1; // 届く最大の位置
        ll reach = -find(i, ub); // max(p[i].first + p[i].second) in [i, ub]
        ll unboot = lower_bound(ALL(pos), reach) - pos.begin();
        update(i, ub, -(p[unboot - 1].first + p[unboot - 1].second));
        mem[i] = mem[i + 1] + mem[unboot];
        mem[i] %= MOD;
    }
    cout << mem[0] << endl;
    return 0;
}

Compiler output:
a.cc: In function 'int find(int, int)':
a.cc:97:47: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
   97 |         for (int i = s; i <= t; i++) ret = min(ret, a[i]);
      |                                            ~~~^~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:97:47: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   97 |         for (int i = s; i <= t; i++) ret = min(ret, a[i]);
      |                                            ~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:97:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   97 |         for (int i = s; i <= t; i++) ret = min(ret, a[i]);
      |                                            ~~~^~~~~~~~~~~
a.cc:102:57: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
  102 |         for (int i = s; i < (st + 1) * B; i++) ret = min(ret, a[i]);
      |                                                      ~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:102:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  102 |         for (int i = s; i < (st + 1) * B; i++) ret = min(ret, a[i]);
      |                                                      ~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:102:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  102 |         for (int i = s; i < (st + 1) * B; i++) ret = min(ret, a[i]);
      |                                                      ~~~^~~~~~~~~~~
a.cc:103:52: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
  103 |         for (int i = gt * B; i <= t; i++) ret = min(ret, a[i]);
      |                                                 ~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:103:52: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  103 |         for (int i = gt * B; i <= t; i++) ret = min(ret, a[i]);
      |                                                 ~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:103:52: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  103 |         for (int i = gt * B; i <= t; i++) ret = min(ret, a[i]);
      |                                                 ~~~^~~~~~~~~~~
a.cc:108:41: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
  108 |             if (lazy[i] == -1) ret = min(ret, mi[i]);
      |                                      ~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:108:41: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  108 |             if (lazy[i] == -1) ret = min(ret, mi[i]);
      |                                      ~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:108:41: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  108 |             if (lazy[i] == -1) ret = min(ret, mi[i]);
      |                                      ~~~^~~~~~~~~~~~
a.cc:110:27: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
  110 |             else ret = min(ret, lazy[i]);
      |                        ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:110:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  110 |             else ret = min(ret, lazy[i]);
      |                        ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _T