제출 #1264799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264799		TsotneSV	Trains (BOI24_trains)	C++20	100 / 100	172 ms	9020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e9,INF=1e18; 

int n;

void solve(int tc = 0){
    cin>>n; vi d(n+1),x(n+1); vector<ll> dp(n+1,0); int root = sqrtl(n + 5);

    vector<vector<ll>> add(root,vector<ll>(root,0));

    ll ans = 0; multiset<array<ll,3>> st; dp[1] = 1;

    rep(i,1,n+1) {
        cin>>d[i]>>x[i];

        while(st.size()) {
            auto [idx,d,sub] = *(st.begin());
            if(idx != i) break;
            st.erase(st.begin()); 
            add[d][idx % d] = (add[d][idx % d] - sub + mod) % mod;
        }

        for(int j=1;j<root;j++) {
            dp[i] = (dp[i] + add[j][i % j]) % mod;
        }


        if(d[i] >= root) {
            for(int j=i+d[i]; (j-i)/d[i] <= x[i] and j <= n; j += d[i]) {
                dp[j] = (dp[j] + dp[i]) % mod;
            }
        } else if(d[i] != 0) {
            ll r = 1ll * min((n - i) / d[i] + 1,x[i] + 1) * d[i] + i;
            st.ins({r,d[i],dp[i]});
            add[d[i]][i % d[i]] = (add[d[i]][i % d[i]] + dp[i]) % mod;
        }

        ans = (ans + dp[i]) % mod;

    } print(ans);

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

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