Submission #1113700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113700		thelegendary08	Trains (BOI24_trains)	C++17	37 / 100	953 ms	504072 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 1e5 + 5;
int tree[mxn * 4];
int n;
void update(int k, int x){
	k += n;
	tree[k] += x;
	tree[k] %= leg;
	for(k/=2; k>=1; k/=2){
		tree[k] = tree[k*2] + tree[k*2 + 1];
		tree[k] %= leg;
	}
}
void rangeupdate(int l, int r, int x){
	if(l <= r){
		update(l, x);
		if(r != n-1)update(r+1, -x);
	}
	
}
int quer(int l, int r){
	l += n;
	r += n;
	int ret = 0;
	while(l <= r){
		if(l % 2 == 1)ret += tree[l++];
		if(r % 2 == 0)ret += tree[r--];
		l/=2;
		r/=2;
	}
	return ret;
}
int pointquer(int x){
	return quer(0, x);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	cin>>n;
	if(n <= 1e4){
		vvi adj(n);
		vi dp(n);
		dp[0] = 1;
		f0r(i,n){
			in2(d,x);
			
			if(d != 0){
				for(int j = i + d; j <= min(n-1, i + d * x); j += d){
					adj[j].pb(i);
				}
			}
			
			
		}
		
		FOR(i, 1, n){
			for(auto u : adj[i]){
				dp[i] += dp[u];
				dp[i] %= leg;
			}
		}
		//vout(dp);
		int sum = 0;
		f0r(i, n){
			sum += dp[i];
			sum %= leg;
		}
		out(sum);
	}
	else{
		rangeupdate(0, 0, 1);
		f0r(i,n){
			in2(d,x);
			//add dp[i] to range [i+1, min(i+x, n-1)]
			rangeupdate(i+1, min(i+x, n-1), pointquer(i));
			//out3(i+1, min(i+x, n-1), pointquer(i));
		}
		int sum = 0;
		f0r(i,n){
			sum += pointquer(i);
			//cout<<pointquer(i)<<' ';
			sum %= leg;
		}
		//out("");
		out(sum);
	}
}

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