제출 #1145450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145450		Rawlat_vanak	Trains (BOI24_trains)	C++20	55 / 100	569 ms	410136 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;

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)); 
		for(int i=1;i<block;i++){
			for(int j=0;j<block;j++){
				bit[i][j].resize(n/i+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++){
			for(int j=1;j<=block-1;j++){
				int start=i%j;
				if(start==0){
					start=j;
				}
				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){
				
				for(int j=i+d[i];j<=min(i+x[i]*d[i],n);j+=d[i]){
					dp[j]=(dp[j]+dp[i])%mod;
				}
			}else{
				int start=i%d[i];
				if(start==0){
					start=d[i];
				}
				int l=i+d[i];
				int r=min(i+x[i]*d[i],n);
				//cout<<l<<' '<<r<<'\n';
				if(l>r) continue;
				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(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;
}

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