Submission #1367335

#TimeUsernameProblemLanguageResultExecution timeMemory
1367335settopTrains (BOI24_trains)C++20
100 / 100
175 ms277380 KiB
#include<bits/stdc++.h>
 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define int long long
#define double long double
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define S second
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=2e5+10;
const int MAXL=19;
const int inf=1e14;
const int MOD=1e9+7;
const int HASHBASE=146527;
const int HASHMOD=1e9+7;
const int SQRT=350;
 
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
typedef tuple<int,int,int,int> squad; 
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,v[MAXN],lim[MAXN],dp[MAXN],somadp[MAXN][SQRT];

int32_t main(){
  std::ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin>>n;
  fall(i,1,n) cin>>v[i]>>lim[i];

  rfall(i,n,1){
    dp[i]=1;
    if(v[i]>=SQRT){
      for(int j=i+v[i];j<=min(n,i+v[i]*lim[i]);j+=v[i]) dp[i]=(dp[i]+dp[j])%MOD;
    }
    else if(v[i]){
      int l=min(i+((n-i)/v[i])*v[i],i+v[i]*lim[i])+v[i];
      dp[i]+=somadp[i+v[i]][v[i]];
      dp[i]-=somadp[l][v[i]];
    }
    dp[i]=(dp[i]%MOD+MOD)%MOD;
    for(int j=1;j<SQRT;j++){
      somadp[i][j]=dp[i]+somadp[i+j][j];
      somadp[i][j]%=MOD;
    }
  } 
  dp[1]+=MOD;
  cout<<dp[1]%MOD<<"\n";
} 
#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...