제출 #1349207

#제출 시각아이디문제언어결과실행 시간메모리
1349207NewtonabcTrains (BOI24_trains)C++20
100 / 100
373 ms45540 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int SQ=350;
const ll MOD=1e9+7;
const int K=340;
const int N=1e5+10;
ll d[N],x[N],ex[N],s[N];
ll cal[SQ][SQ],act[SQ][SQ];
vector<tuple<int,int,ll>> out[N];
vector<int> ci[N];
int main(){
    int n; cin>>n;
    s[1]=1;
    for(int i=1;i<=n;i++){
        cin>>d[i] >>x[i];
        if(d[i]==0 || x[i]==0 || d[i]>n-i) continue;
        if(d[i]>=K){
            for(int j=i+d[i];j<=min((ll)n,(ll)i+d[i]*x[i]);j+=d[i]){
                ci[j].push_back(i);
            }
        }
    }
    for(int i=1;i<=n;i++) sort(ci[i].begin(),ci[i].end()),ci[i].erase(unique(ci[i].begin(),ci[i].end()),ci[i].end());
    for(int i=1;i<=n;i++){
        for(int j=1;j<SQ;j++){
            if(act[j][i%j]) s[i]=(s[i]+cal[j][i%j])%MOD;
        }
        for(auto c:ci[i]) s[i]=(s[i]+s[c])%MOD;
        for(int j=1;j<SQ;j++){
            if(d[i]==j && d[i]<K){
                cal[j][i%j]=(cal[j][i%j]+s[i])%MOD;
                out[min((ll)n,(ll)i+d[i]*x[i])].push_back({j,i%j,s[i]});
            }
            
        }
        if(d[i]<K && d[i]!=0) act[d[i]][i%d[i]]++;
        for(auto [x,y,val]:out[i]){
            cal[x][y]=(cal[x][y]+MOD-val)%MOD;
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++) sum+=s[i],sum%=MOD;
    cout<<sum <<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...