Submission #1367270

#TimeUsernameProblemLanguageResultExecution timeMemory
1367270julia_08Trains (BOI24_trains)C++20
100 / 100
1327 ms627628 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 3e5 + 10;
const int SQ = 540;

const ll MOD = 1e9 + 7;

int d[MAXN], x[MAXN];

ll dp[MAXN];

vector<ll> sum[SQ][SQ];

int n;

void update(int i){

  for(int j=1; j<SQ; j++){

    ll cur = (sum[j][i % j].back() + dp[i]) % MOD;
    sum[j][i % j].push_back(cur);

  }

}

ll get_sum(int d, int i, int x){

  if(!d) return 0;

  ll ans = 0;

  if(d >= SQ){

    int j = i + d;

    while(j <= min((ll) n, i + (ll) d * x)){
      ans = (ans + dp[j]) % MOD;
      j += d;
    }

    return ans;

  }

  int sz = (int) sum[d][i % d].size();

  ans = sum[d][i % d][sz - 1];

  int pos = max(0, sz - x - 1);
  ans = (ans - sum[d][i % d][pos] + MOD) % MOD;

  return ans;

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;

  for(int i=1; i<=n; i++) cin >> d[i] >> x[i];

  for(int i=1; i<SQ; i++){
    for(int j=0; j<i; j++){
      sum[i][j].push_back(0);
    }
  }

  dp[n] = 1;
  update(n);

  for(int i=(n - 1); i>=1; i--){

    dp[i] = (1 + get_sum(d[i], i, x[i])) % MOD;
    update(i);

    // cout << "dp[" << i << "] = " << dp[i] << endl;

  }

  cout << dp[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...