Submission #1033613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033613		cnn008	Trains (BOI24_trains)	C++17	100 / 100	155 ms	10748 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif

#define int long long

const int N=1e5+5;
const int mod=1e9+7;
const int sz=320;	

int n,d[N],x[N],en[N];
vector <pair <int,int> > v[N];
namespace sub1{
	bool ck(){
		return n<=10000;
	}
	int dp[N];
	void sol(){
		dp[1]=1;
		for(int i=2; i<=n; i++){
			for(int j=1; j<i; j++){
				if(d[j] and (i-j)%d[j]==0 and en[j]>=i) dp[i]=(dp[i]+dp[j]<mod?dp[i]+dp[j]:dp[i]+dp[j]-mod);
			}
		}
		int ans=0;
		for(int i=1; i<=n; i++) ans=(ans+dp[i]<mod?ans+dp[i]:ans+dp[i]-mod);
		cout<<ans;
	}
}
namespace sub2{
	bool ck(){
		for(int i=1; i<=n; i++) if(d[i]!=1) return 0;
		return 1;
	}
	struct BIT{
		#define gb(x) (x)&(-x)
		int n;
		vector <int> bit;
		void init(int _n){
			n=_n;
			bit.resize(_n,0);
		}
		void update(int i, int v){
			for(; i<n; i+=gb(i)) bit[i]=(bit[i]+v)%mod;
		}
		void range(int l, int r, int v){
			if(l>r) return;
			update(l,v);
			update(r+1,-v);
		}
		int get(int i){
			int ans=0;
			for(; i; i-=gb(i)) ans=(ans+bit[i])%mod;
			return ans;
		}
	}fw;
	int dp[N];
	void sol(){
		fw.init(n+5);
		dp[1]=1;
		fw.range(2,en[2],1);
		int ans=1;
		for(int i=2; i<=n; i++){
			dp[i]=(fw.get(i)-fw.get(i-1)+mod)%mod;
			fw.range(i+1,en[i],dp[i]);
			ans=(ans+dp[i])%mod;
		}
		cout<<ans;
	}
}
namespace full{
	int dp[N],g[sz+5][sz+5],ans;
	void sol(){
		dp[1]=1;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=sz; j++){
				dp[i]=(dp[i]+g[j][i%j])%mod;
			}
			if(d[i]>sz){
				for(int j=i+d[i]; j<=en[i]; j+=d[i]) dp[j]=(dp[j]+dp[i])%mod;
			}else if(d[i]>0){
				g[d[i]][i%d[i]]=(g[d[i]][i%d[i]]+dp[i])%mod;
			}
			for(auto [j,_d]:v[i]) if(_d<=sz) g[_d][j%_d]=(g[_d][j%_d]-dp[j]+mod)%mod;
		}
		for(int i=1; i<=n; i++) ans=(ans+dp[i])%mod;
		cout<<ans;
	}
}
void sol(){
	cin>>n;
	for(int i=1; i<=n; i++) cin>>d[i]>>x[i],en[i]=min(n,i+d[i]*x[i]);
	for(int i=1; i<=n; i++) if(d[i] and d[i]<=sz) v[en[i]].push_back({i,d[i]});
	// if(sub1::ck()){
		// sub1::sol();
		// return;
	// }
	// if(sub2::ck()){
		// sub2::sol();
		// return;
	// }
	full::sol();
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("arya.inp", "r", stdin);
    // freopen("arya.out", "w", stdout);
    int tt=1;
    //cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

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