Submission #1145457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145457		Rawlat_vanak	Trains (BOI24_trains)	C++20	16 / 100	16 ms	3656 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<int,int>
#define pb push_back



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

const int block=100,mod=1000000007;

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)%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)%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)+mod)%mod;
			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)%mod;
			//cout<<dp[i]<<' ';
		}
		cout<<final<<'\n';
		




		



		
		



		



	
	
	


		

		

	}
	return 0;
}

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