제출 #1367317

#제출 시각아이디문제언어결과실행 시간메모리
1367317talyTrains (BOI24_trains)C++20
16 / 100
30 ms5908 KiB
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define int long long
using namespace std;
int mod=1e9+7;
vector<int> tree;

void upd(int x, int l, int r, int node, int v){
    if(x<l||x>r)return;
    if(l==r){
        tree[node]+=v;
        return;
    }
    int m=(l+r)/2;
    upd(x, l, m, 2*node+1, v);
    upd(x, m+1, r, 2*node+2, v);
    tree[node]=tree[2*node+1]+tree[2*node+2];
}

int query(int ll, int lr, int l, int r, int node){
    if(ll>r||lr<l)return 0;
    if(ll<=l&&lr>=r){
        return tree[node];
    }
    int m=(l+r)/2;
    return (query(ll, lr, l, m, 2*node+1)+query(ll, lr, m+1, r, 2*node+2))%mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    tree.resize(4*(n+1));
    vector<int> d(n+1), x(n+1);
    for(int i=1; i<=n; i++){
        cin >> d[i] >> x[i];
    }
    int resp=0;
    vector<int> r(n+1);
    for(int i=n; i>=1; i--){
        if(d[i]!=0){
            r[i]=query(i, i+x[i], 1, n, 0);
            // for(int j=i; j<=n&&j<=x[i]*d[i]+i; j+=d[i]){
            //     r[i]=(r[i]+r[j])%mod;
            //     // cout << i << ": "<<j<<endl;
            // }
        }
        r[i]++;
        r[i]%=mod;
        upd(i, 1, n, 0, r[i]);
        // cout << i << " "<<r[i]<<endl;
        // resp=(resp+r[i])%mod;
    }
    cout << r[1]<<endl;

}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…