Submission #1033643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033643		vjudge1	Trains (BOI24_trains)	C++17	37 / 100	2049 ms	6884 KiB

Main

#include <bits/stdc++.h>
#define ll long long int
#define ii long long int
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define ins insert
#define pf push_front
#define bit(n,k) ((n>>k)&1)
#define pi acos(-1.0)
const ll N=1e5+5, inf = 1e9, mod=1e9+7;
using namespace std;
ii t[4*N],lz[4*N];
void pus(ii v, ii l, ii r){
    if(lz[v]==0) return;
    t[v]+=(r-l+1)*lz[v];
    t[v]%=mod;
    if(l!=r){
        lz[v<<1]+=lz[v];
        lz[v<<1|1]+=lz[v];
        lz[v<<1]%=mod;
        lz[v<<1|1]%=mod;
    }
    lz[v]=0;
}
void update(ii v, ii l, ii r, ii x, ii y, ii val){
    pus(v,l,r);
    if(l>y||r<x) return;
    if(x<=l&&r<=y){
        lz[v]+=val;
        lz[v]%=mod;
        pus(v,l,r);
        return;
    } 
    ii mid=(l+r)>>1;
    update(v<<1,l,mid,x,y,val);
    update(v<<1|1,mid+1,r,x,y,val);
    t[v]=(t[v<<1]+t[v<<1|1])%mod;
}
ii get(ii v, ii l, ii r, ii x, ii y){
    pus(v,l,r);
    if(l>y||r<x) return 0;
    if(x<=l&&r<=y) return t[v];
    ii mid=(l+r)>>1;
    return (get(v<<1,l,mid,x,y)+get(v<<1|1,mid+1,r,x,y))%mod; 
}
int main(){
    // freopen("TRAVEL.INP", "r", stdin);
    // freopen("TRAVEL.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);  
    ii n; cin >> n;
    pair<ii,ii>a[n+1];
    ii dp[n+1];
    bool sub3=true;
    for(ii i=1;i<=n;i++){
        cin >> a[i].fi >> a[i].se;
        dp[i]=0;
        if(a[i].fi!=1) sub3=false;
    }
    if(sub3){
        update(1,1,n,1,1,1);
        for(ii i=1;i<=n;i++){
            update(1,1,n,i+1,i+a[i].se,get(1,1,n,i,i));
        }
        cout << get(1,1,n,1,n) << endl;
    }
    else{
        dp[1]=1;
        for(ii i=1;i<=n;i++){
            if(a[i].fi==0) continue;
            for(ii j=1;j<=a[i].se;j++){
                if(i+j*a[i].fi>n) break;
                dp[i+j*a[i].fi]+=dp[i];
                dp[i+j*a[i].fi]%=mod;
            }
        }
        ii res=0;
        for(ii i=1;i<=n;i++){
            res+=dp[i];
            res%=mod;
        }
        cout << res << endl;
    }
}

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