| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1085873 | De3b0o | Trains (BOI24_trains) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
using namespace std;
const ll sz = 40;
ll seg[sz+1][sz+1][100009];
ll lazy[sz+1][sz+1][100009];
ll ans[100009] , d[100009] , x[100009];
ll n;
const ll m = 1e9+7;
void se(ll j , ll md , ll x , ll l , ll r , ll l1 , ll r1 , ll val)
{
if(l>r1||r<l1)
return;
if(l>=l1&&r<=r1)
{
lazy[j][md][x]=(lazy[j][md][x]+val)%m;
return;
}
se(j,md,lc,l,mid,l1,r1,val);
se(j,md,rc,mid+1,r,l1,r1,val);
}
ll sg(ll j , ll md , ll x , ll l , ll r , ll idx)
{
if(l>idx||r<idx)
return 0;
if(l==r)
{
seg[j][md][x]+=lazy[j][md][x];
lazy[j][md][x]=0;
seg[j][md][x]%=m;
return seg[j][md][x];
}
lazy[j][md][lc]=(lazy[j][md][lc]+lazy[j][md][x])%m;
lazy[j][md][rc]=(lazy[j][md][rc]+lazy[j][md][x])%m;
lazy[j][md][x]=0;
return sg(j,md,lc,l,mid,idx) + sg(j,md,rc,mid+1,r,idx);
}
int main()
{
d3
cin >> n;
for(int i = 0 ; n>i ; i++)
cin >> d[i] >> x[i];
ans[0]=1;
ll an = 0;
for(int i = 0 ; n>i ; i++)
{
for(int j = 1 ; sz>=j ; j++)
{
ll md = i%j;
ans[i]+=sg(j,md,1,0,(n-md-1),i/j);
}
ans[i]%=m;
ll s = min((n-i+1)/d[i],x[i]);
if(s<=100000/sz)
{
for(int j = i+d[i] ; x[i]-- ; j+=d[i])
ans[j]=ans[i];
continue;
}
for(int j = 1 ; sz>=j ; j++)
{
ll md = i%j;
se(j,md,1,0,(n-md-1)/j,i/j,min(i/j+x[i],(n-md-1)/j),ans[i]);
}
an+=ans[i];
an%=m;
}
cout << an;
}