Submission #1033622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033622		idkman	Trains (BOI24_trains)	C++17	24 / 100	46 ms	6768 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll  i=(a);i<=(b);i++)
#define Ford(i,a,b) for(ll  i=(a);i>=(b);i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define endl "\n"
using namespace std;
int Dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
int Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
const ll inf = 1000000000000000000;
const int N = 100000;
const int block_size = 300;
const ll MOD =  1e9 + 7; /* 998244353 */
const int LG = 18;
const int K = 20;	
const int M = 100000;
ll nph(ll k, ll x) { return ((x >> k) & 1LL); }
ll n,d[N+3],x[N+3],st[4*N], dp[N+3];
void update(ll idx, ll l, ll r, ll x) {
	if(l > x || r < x) return;
	if(l == r) {
		st[idx] = dp[x];
		return;
	}
	ll md = l + r >> 1;
	update(2*idx, l, md, x);
	update(2*idx+1, md+1, r, x);
	st[idx] = st[2*idx] + st[2*idx+1];
}

ll get(ll idx, ll l, ll r, ll u, ll v) {
	if(l > v || r < u) return 0;
	if(u <= l && r <= v) return st[idx];
	ll md = l + r >> 1;
	return get(2*idx, l, md, u, v) + get(2*idx+1, md+1, r, u, v);
}
void Solve() { 
	cin>>n;
	For(i, 1, n) cin>>d[i]>>x[i];
	bool sub3 = true;
	For(i, 1, n) if(d[i] != 1) sub3 = false;
	if(n <= 1000) {
		ll dp[n+3];
		Ford(i, n, 1) {
			//if(d[i] == 0) { dp[i] = 0; continue; }
			dp[i] = 1;
			if(d[i] == 0) continue;
			ll j = 1;
			while(i + j*d[i] <= n && j <= x[i]) {
				dp[i] += dp[i+j*d[i]];
				dp[i] %= MOD;
				j++;
			}
		}
		cout << dp[1]; return;
	}
	if(sub3) {
		Ford(i, n, 1) {
			dp[i] = 1;
			if(d[i] == 0) {update(1, 1, n, i); continue;}
			if(i+1 <= min(n, i+x[i])) dp[i] += get(1, 1, n, i+1, min(n, i+x[i]));
			dp[i] %= MOD;
			update(1, 1, n, i);
		}
		cout << dp[1];
	}
}	

int main() {
    // freopen("PHOTO.INP", "r", stdin);
    // freopen("PHOTO.OUT", "w", stdout);
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int t = 1;
    //cin >> t; 
    while(t--) 
    	Solve();
}

Compilation message (stderr)

Main.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
Main.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  ll md = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  ll md = l + r >> 1;
      |          ~~^~~

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