제출 #1028710

#제출 시각아이디문제언어결과실행 시간메모리
1028710isaachewTrains (BOI24_trains)C++17
100 / 100
145 ms5924 KiB
#include <bits/stdc++.h>
/*
 Go from city i to i + k*d_i
 Sqrt
 
 */
int midc=300;
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    std::vector<std::vector<int>> mods(1);
    std::vector<int> specials(n);
    std::vector<std::vector<std::pair<int,int>>> events(n);
    for(int i=1;i<=midc;i++){
        mods.emplace_back(i+1);
    }
    int result=0;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        int curtot=(i==0);
        for(int j=0;j<midc;j++){
            curtot+=mods[j+1][i%(j+1)];
            curtot%=1000000007;
        }
        curtot+=specials[i];
        curtot%=1000000007;
        result+=curtot;
        result%=1000000007;
        if(a>0){
            if(a<=midc){
                mods[a][i%a]+=curtot;
                mods[a][i%a]%=1000000007;
                if(i+(long long)a*b<n)events[i+a*b].push_back({a,(1000000007-curtot)%1000000007});
            }else{
                for(int j=1;j<=b&&(i+(long long)a*j)<n;j++){
                    specials[i+a*j]+=curtot;
                    specials[i+a*j]%=1000000007;
                }
            }
        }
        for(std::pair<int,int> j:events[i]){
            mods[j.first][i%j.first]+=j.second;
            mods[j.first][i%j.first]%=1000000007;
        }
    }
    std::cout<<result<<'\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...