제출 #1268599

#제출 시각아이디문제언어결과실행 시간메모리
1268599gry3125Trains (BOI24_trains)C++20
100 / 100
181 ms6400 KiB
#include <bits/stdc++.h>
#define ll long long int
#define fi first
#define se second
using namespace std;

ll dp[500][500] = { }, ans[200005] = { };
priority_queue<pair<pair<ll,ll>,pair<ll,ll>>, vector<pair<pair<ll,ll>,pair<ll,ll>>>, greater<pair<pair<ll,ll>,pair<ll,ll>>>> ev;

int main() {
    ll n; cin >> n; ans[1] = 1; ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        ll d, x; cin >> d >> x;
        for (ll j = 1; j*j < n; j++) {
            ans[i] += dp[i%j][j];
            ans[i] %= 1000000007;
        }
        if (d*d >= n) {
            for (ll j = 1; j <= x && i+j*d <= n; j++) {
            	ans[i+j*d] += ans[i];
            	ans[i+j*d] %= 1000000007;
            }
        } else if (d > 0) {
            dp[i%d][d] += ans[i];
            dp[i%d][d] %= 1000000007;
            ev.push({{i+x*d,ans[i]},{i%d,d}});
        }
        while (!ev.empty() && ev.top().fi.fi <= i) {
            auto cur = ev.top(); ev.pop();
            dp[cur.se.fi][cur.se.se] -= cur.fi.se;
            while (dp[cur.se.fi][cur.se.se] < 0) {
                dp[cur.se.fi][cur.se.se] += 1000000007;
            }
        }
        sum += ans[i]; sum %= 1000000007;
    }
    cout << sum;
    return 0;
}
#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...