Submission #1367319

#TimeUsernameProblemLanguageResultExecution timeMemory
1367319lucaskojimaTrains (BOI24_trains)C++20
16 / 100
13 ms2772 KiB
#include "bits/stdc++.h"

#define int long long

using namespace std;

const int MOD = 1e9 + 7;

struct fenwick {
  int n;
  vector<int> b;
  fenwick(int n) : n(n), b(n + 1) {}

  void update(int i, int x) {
    for (; i <= n; i += i & -i)
      b[i] = (b[i] + x) % MOD;
  }
  int query(int i) {
    int res = 0;
    for (; i >= 1; i -= i & -i)
      res = (res + b[i]) % MOD;
    return res;
  }
  int query(int l, int r) {
    return (query(r) - query(l - 1) + MOD) % MOD;
  }
};

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n; cin >> n;

  vector<pair<int, int>> a(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> a[i].first >> a[i].second;

  fenwick fen(n);
  for (int i = 1; i <= n; i++)
    fen.update(i, 1);

  for (int i = n - 1; i >= 1; i--) {
    auto [d, x] = a[i];
    if (x == 0) continue;
    fen.update(i, fen.query(i + 1, min(i + x, n)));
  }

  cout << fen.query(1) << '\n';
  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...