제출 #1028183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028183		underwaterkillerwhale	Trains (BOI24_trains)	C++17	100 / 100	291 ms	5200 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const ll INF = 1e12;
const int BASE = 1337;

struct Data {
    ll D, x;
};

int n;
Data a[N];

namespace sub2 {
    ll dp[N];
    void solution() {
        dp[1] = 1;
        rep (i, 2, n) {
            rep (j, 1, i - 1) {
                if (a[j].D == 0) continue;
                if ((i - j) % a[j].D == 0 && (i - j) / a[j].D <= a[j].x) {
                    (dp[i] += dp[j]) %= Mod;
                }
            }
        }
        ll res= 0;
        rep (i, 1, n) {
            (res += dp[i]) %= Mod;
//            cout << i <<" "<<dp[i] <<"\n";
        }
        cout << res <<"\n";
    }
}

namespace sub5 {

    void inline add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
    void inline sub (int &a, int b) { a -= b; if (a < 0) a += Mod; }

    int dp[N];
    int val[szBL + 7][szBL + 7];
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> st[szBL + 7];

    void solution() {
        dp[1] = 1;
        rep (i, 1, n) {
            rep (D, 1, szBL) {
                while (!st[D].empty() && st[D].top().fs < i) {
                    pair<int,int> cur = st[D].top();
                    st[D].pop();
                    sub(val[D][cur.se%D], dp[cur.se]);
                }
//                if (i == 5) cout << "hihi: "<<D<<" "<<val[D][i%D]<<"\n";
                add(dp[i], val[D][i%D]);
            }
            if (a[i].D == 0) continue;
            if (a[i].D <= szBL) {
                st[a[i].D].push(mp(min(1LL * a[i].x * a[i].D + i, 1LL * n + 1), i));
                add(val[a[i].D][i % a[i].D], dp[i]);
            }
            else {
                rep (k, 1, a[i].x) {
                    if (i + 1LL * k * a[i].D > n) break;
                    add(dp[i + k * a[i].D], dp[i]);
                }
            }
        }
        int res = 0;
        rep (i, 1, n) {
            add(res, dp[i]);
//            cout << i <<" "<<dp[i] <<"\n";
        }
        cout << res <<"\n";
    }
}

void solution () {
    cin >> n;
//    n = 10;
    rep (i, 1, n) {
        cin >> a[i].D >> a[i].x;
//        a[i].D = Rand(1, 5);
//        a[i].x = Rand(1, 100);
    }
    if (n <= 1e4)
        sub2 :: solution();
//    cout<<"\n";
    else if (n <= 1e5)
        sub5 :: solution();
}

#define file(name) freopen(name".inp", "r", stdin); \
//freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/

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