Submission #1128999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128999		nhanhoang510	Trains (BOI24_trains)	C++20	100 / 100	125 ms	9156 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

int add(int a, int b){
    if(a + b < MOD)
        return a + b;
    return a + b - MOD;
}

int sub(int a, int b){
    if(a - b >= 0)
        return a - b;
    return a - b + MOD;
}

int n;
int num[maxn], d[maxn];

namespace SUB1{

int f[maxn];

void solve(){
    memset(f, 0, sizeof(f));
    f[1] = 1;
    for(int i = 1; i < n; ++i) if(d[i] != 0){
        for(int k = 1; k <= num[i] && i + k * d[i] <= n; ++k){
            f[i + k * d[i]] = add(f[i + k * d[i]], f[i]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans = add(ans, f[i]);
    cout << ans << "\n";
    return;
}

}

namespace FULL{

const int maxSQRT = 400 + 7;
const int LIM = 320;

int f[maxn];
int g[maxSQRT][maxSQRT];
vector<int> del[maxn];

void solve(){
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for(int i = 1; i <= n; ++i)
        del[i].clear();
    f[1] = 1;
    for(int i = 1; i <= n; ++i){
        for(int dd = 1; dd <= LIM; ++dd){
            f[i] = add(f[i], g[dd][i % dd]);
        }
        if(d[i] != 0 && num[i] != 0){
            int dd = d[i];
            if(dd > LIM){
                for(int k = 1; k <= num[i] && i + k * dd <= n; ++k){
                    f[i + k * dd] = add(f[i + k * dd], f[i]);
                }
            } else{
                g[dd][i % dd] = add(g[dd][i % dd], f[i]);
                long long pos = 1LL * dd * num[i] + i;
                if(pos <= n)
                    del[pos].push_back(i);
            }
        }
        for(int id : del[i]){
            int dd = d[id];
            g[dd][id % dd] = sub(g[dd][id % dd], f[id]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans = add(ans, f[i]);
    cout << ans << "\n";
    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("Trains.INP","r",stdin);
    // freopen("Trains.OUT","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> d[i] >> num[i];
    if(n <= 10000)
        SUB1::solve();
    else
        FULL::solve();
    return 0;
}

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