Submission #1302201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302201		KindaGoodGames	Trains (BOI24_trains)	C++20	100 / 100	272 ms	7720 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int,int>
#define tiiii tuple<int,int,int,int> 

int mod = 1e9+7;

struct SegmentTree{
    vector<int> S;
    int len = 1;

    SegmentTree(int n){
        while(len < n) len <<= 1;

        S.resize(2*len);
    }

    int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;
        if(ql <= l && r <= qr) return S[i];
        if(r <= ql || qr<= l) return 0;
        int mid = (l+r)/2;
        
        return (query(ql,qr,l,mid,i)+query(ql,qr,mid,r,i*2+1))%mod;
    }

    void upd(int i, int v){
        i += len;
        S[i] += mod+v;
        S[i] %= mod;
        for(i /= 2; i > 0; i /= 2){
            S[i] = (S[i*2]+S[i*2+1])%mod;
        }
    }
};

int32_t main(){
    int n;
    cin >> n;

    //int rt = sqrt(n)+1;
    int rt = sqrt(n)+1;

    vector<pii> arr(n);

    for(int i = 0; i < n; i++){
        int a,b;
        cin >> a >> b; 
        arr[i]= {a,b};
    }

    vector<vector<int>> delta(rt+1, vector<int>(rt));  
    priority_queue<tiiii, vector<tiiii>, greater<tiiii>> pq;
    vector<int> dp(n+1);
    int s = 0;
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        int d,x;
        tie(d,x) = arr[i]; 
        while(pq.size() && get<0>(pq.top()) <= i){
            int l,del,k,p;
            tie(l,del,k,p) = pq.top(); pq.pop();
            delta[k][p] = (mod+delta[k][p]-del)%mod;
        }
        for(int k = 1; k <= rt; k++){
            dp[i] += delta[k][i%k];
            dp[i] %= mod; 
        }
        
        s += dp[i];
        s %= mod;

        if(d == 0) continue;

        if(d > rt){
            int c = 0;
            int pt = i;
            while(c < x){
                c++;
                pt += d;
                if(pt >= n) break;

                dp[pt] += dp[i];
                dp[pt] %= mod;
            }
        }else{
            // increase current delta by the amount of paths there are until the current node
            delta[d][i%d] += dp[i];
            // after i+(x*d), the path is invalid
            pq.push({i+(x*d)+1,dp[i],d,i%d});
            delta[d][i%d] %= mod;
        }
    }
    assert(s >= 0 && s <mod);
    cout << s << "\n";
}

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