Submission #1145456

#TimeUsernameProblemLanguageResultExecution timeMemory
1145456Rawlat_vanakTrains (BOI24_trains)C++20
0 / 100
12 ms2888 KiB
#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<int,int>
#define pb push_back

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

const int block=100;

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

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


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

		for(int i=1;i<=n;i++){
			dp[i]=(dp[i]+get(i,1,1));
			if(d[i]==0) continue;
			int l=i+1;
			int r=min(n,i+x[i]);
			if(l<=r){
			  update(l,dp[i],1,1);
			  if(r<n){
			    update(r+1,-dp[i],1,1);
			  }
			}
		}
		/*cout<<'\n';

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




		



		
		



		



	
	
	


		

		

	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...