제출 #1355866

#제출 시각아이디문제언어결과실행 시간메모리
1355866AvianshTrains (BOI24_trains)C++20
100 / 100
122 ms7664 KiB
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int mod = 1e9+7;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int sq = ceil(sqrt(n));
    int laz[sq][sq];
    for(int i = 0;i<sq;i++){
        fill(laz[i],laz[i]+sq,0);
    }
    vector<array<int,3>>rem[n];
    long long dp[n];
    fill(dp,dp+n,0);
    dp[0]=1;
    for(int i = 0;i<n;i++){
        int d,x;
        cin >> d >> x;
        long long curr = 0;
        for(int j = 0;j<sq;j++){
            ///j=0 corresponds to j+1.
            curr+=laz[j][(i%(j+1))];
            curr%=mod;
        }
        dp[i]+=curr;
        dp[i]%=mod;
        ///first take care of rem.
        for(array<int,3>a:rem[i]){
            laz[a[0]][a[1]]-=a[2];
            laz[a[0]][a[1]]%=mod;
        }
        ///now put this somewhere
        if(d&&x){
            if(d<sq){
                ///do lazy ENSURE to add to rem as well
                int las = i+(d*x);
                las=min(las,n-1);
                laz[d-1][i%d]+=dp[i];
                rem[las].push_back({d-1,i%d,dp[i]});
            }
            else{
                ///just bruteforce
                for(int j = 1;j<=x;j++){
                    int ind = i+d*j;
                    if(ind>=n)
                        break;
                    dp[ind]+=dp[i];
                    dp[ind]%=mod;
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 0;i<n;i++){
        ans+=dp[i];
        ans%=mod;
    }
    ans+=mod;
    ans%=mod;
    cout << ans;
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…