Submission #1028710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028710		isaachew	Trains (BOI24_trains)	C++17	100 / 100	145 ms	5924 KiB

Main

#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';
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29