| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1297568 | matematteo | Trains (BOI24_trains) | C++20 | 0 ms | 0 KiB |
// NOTE: it is recommended to use this even if you don't understand the
// following code.
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
const long long mod=1e9+7;
struct nd{
long long d, x;
vector<long long>sus;
vector<long long>flag;
};
int main() {
#define int long long
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, Q;
cin >> N;
int d=sqrt(N);
vector<long long>dp(N);
vector<nd>t(N);
for (int a,b,i=0;i<N;i++){
cin >> a >> b;
t[i].d=a; t[i].x=min(N,b);
t[i].sus.resize(d);
}
dp[0]=1;
long long sum=0;
for (int i=0;i<N;i++){
for (int j=0;j<d;j++){
dp[i]+=t[i].sus[j];
dp[i]%=mod;
}
if (t[i].d>=d){
int j=i;
j+=t[i].d;
int s=1;
while (j<N&&s<=t[i].x){
dp[j]+=dp[i];
dp[j]%=mod;
j+=t[i].d;
s++;
}
}
else{
if (i+t[i].d*t[i].x<N){
t[i+t[i].d*t[i].x].flag.push_back(i);
}
t[i].sus[t[i].d]+=dp[i]; t[i].sus[t[i].d]%=mod;
}
for (auto u:t[i].flag){
t[i].sus[t[u].d]-=dp[u]; t[i].sus[t[u].d]+=mod; t[i].sus[t[u].d]%=mod;
}
if (i!=N-1){
t[i+1].sus=t[i].sus;
}
sum+=dp[i]; sum%=mod;
}
//for (int i=0;i<N;i++) cout << dp[i] << " "; cout << endl;
cout << sum;
return 0;
} return 0;
}
