Submission #1145415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145415		Rawlat_vanak	Trains (BOI24_trains)	C++20	21 / 100	536 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<long long int,long long int>
#define pb push_back

vector<vector<vector<int>>> bit;//step,start,value

const long long int block=100;

void update(long long int idx, long long int val, long long int step, long long int start){
	while(idx<=bit[step][start].size()){
		bit[step][start][idx]=(bit[step][start][idx]+val)%mod;
		idx+=idx&(-idx);
	}
}

long long int get(long long int idx, long long int step, long long int start){
	long long int ans=0;
	while(idx>0){
		ans=(ans+bit[step][start][idx])%mod;
		idx-=(idx)&(-idx);
	}
	return ans;
}


int32_t main(){
	speedIO;
	long long int t,n,m,k,q;
	//cin>>t;
	t=1;
	while(t--){
		cin>>n;
		vector<long long int> d(n+1),x(n+1),dp(n+1,0);
		bit.resize(block,vector<vector<int>>(block,vector<int>(n+5,0))); 
		for(long long int i=1;i<=n;i++){
			cin>>d[i]>>x[i];
		}
		dp[1]=1;
		//update(1,1,1);

		for(long long int i=1;i<=n;i++){
			for(long long int j=1;j<=block-1;j++){
				long long int start=i%j;
				if(start==0){
					start=j;
				}
				long long int tmp=i-start;
				tmp/=j;
				tmp+=1;
				//if(j<6) cout<<"hi "<<i<<' '<<tmp<<' '<<j<<' '<<start<<'\n';
				//if(j<6) cout<<"what "<<get(tmp,j,start)<<'\n';
				dp[i]=(dp[i]+get(tmp,j,start))%mod;
			}
			if(d[i]==0) continue;
			if(d[i]>=block){
				/*long long long long int wow=x[i]*d[i];
				long long int wew=wow;
				if(i+wow>n){
					long long int wew=n-i;
				}*/
				for(long long int j=i+d[i];j<=min(i+d[i]*x[i],n);j+=d[i]){
					dp[j]=(dp[j]+dp[i])%mod;
				}
			}else{
				long long int start=i%d[i];
				if(start==0){
					start=d[i];
				}
				long long int l=i+d[i];
				/*long long long long int wow=x[i]*d[i];
				long long int wew=wow;
				if(i+wow>n){
					long long int wew=n-i;
				}*/
				long long int r=min(i+d[i]*x[i],n);
				//cout<<l<<' '<<r<<'\n';
				if(l>r) continue;
				long long int tmp=l-start;
				tmp/=d[i];
				tmp+=1;
				//cout<<tmp<<' '<<dp[i]<<' '<<d[i]<<' '<<start<<'\n';
				update(tmp,dp[i],d[i],start);
				if(r==n){
					//update(n,-dp[i],d[i],start);
				}else{			
					tmp=r-start;
					tmp/=d[i];
					tmp+=2;
					//cout<<tmp<<' '<<-dp[i]<<' '<<d[i]<<' '<<start<<'\n';
					update(tmp,-dp[i],d[i],start);
				}
			}
		}
		/*cout<<'\n';

		for(long long int i=0;i<=n+3;i++){
			cout<<bit[1][1][i]<<' ';
		}
		cout<<'\n';
		cout<<get(5,1,1)<<'\n';*/
		long long int final=0;
		for(long long int i=1;i<=n;i++){
			final=(final+dp[i])%mod;
			//cout<<dp[i]<<' ';
		}
		cout<<final<<'\n';
		




		



		
		



		



	
	
	


		

		

	}
	return 0;
}

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