Submission #1349167

#TimeUsernameProblemLanguageResultExecution timeMemory
1349167NewtonabcTrains (BOI24_trains)C++20
0 / 100
46 ms2052 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 act[SQ][SQ];
vector<pair<int,int>> 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) continue;
        if(d[i]>=2e5){
            for(int j=i+d[i];j<=min((ll)n,(ll)i+d[i]*x[i]);j+=d[i]){
                ci[j].push_back(j-d[i]);
            }
        }
        else{
            out[min((ll)n,(ll)i+d[i]*x[i])].push_back({d[i],i%d[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++){
        vector<int> add;
        for(int j=1;j<SQ;j++){
            if(i-j>=1 && act[j][i%j]) add.push_back(i-j);
        }
        for(auto c:ci[i]) add.push_back(c);
        sort(add.begin(),add.end());
        add.erase(unique(add.begin(),add.end()),add.end());
        for(auto c:add) s[i]=(s[i]+s[c])%MOD;
        if(d[i]<K && d[i]!=0) act[d[i]][i%d[i]]++;
        for(auto [x,y]:out[i]) act[x][y]--;
        //cout<<s[i] <<" ";
    }
    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...