Submission #1052740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052740		Nonoze	Trains (BOI24_trains)	C++17	100 / 100	364 ms	255296 KiB

Main

/*
*	Author: Nonoze
*	Created: Sunday 05/05/2024
*/
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long


#ifndef _IN_LOCAL
	#define dbg(...) ;
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) {cout << x << endl; return;}
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;

int mod(int x) {
	return ((x%MOD)+MOD)%MOD;
}

void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, m, q;
const int k=320;
vector<int> a, d, sz, idx;
int sum[k][k][k], block[k][k];

void build() {
	sz.resize(k), idx.resize(k);
	for (int i=0; i<n; i++) {
		if (!sz[i/k]) idx[i/k]=i;
		sz[i/k]++;
	}
}

int get(int pos) {
	int bpos=pos%k;
	int ans=block[pos/k][bpos];
	if (!pos) ans=mod(ans+1);
	for (int i=1; i<k; i++) {
		ans+=sum[pos/k][i][bpos%i];
		mod(ans);
	}
	return mod(ans);
}

int solveboth(int nb, int pos, int start, int end) {
	for (int i=start+1; i<k && idx[i]<=end; i++) {
		int l=idx[i], r=l+sz[i]-1;
        int empl = (idx[i] - pos) / d[pos] + ((idx[i] - pos) % d[pos] != 0);
        empl *= d[pos];
        empl += pos;
		// if (empl<l) empl+=d[pos];
		if (empl>r) continue;
		int bpos=empl%k;
		if (r>end || d[pos]>=k) {
			for (int j=bpos; j<k && idx[i]+j<=end; j+=d[pos]) {
				block[i][j]+=nb;
				mod(block[i][j]);
			}
			continue;
		}
		sum[i][d[pos]][bpos%d[pos]]+=nb;
		mod(sum[i][d[pos]][bpos%d[pos]]);
	}
	return nb;
}

int update(int pos) {
	if (!d[pos]) return get(pos);
	int start=pos/k, end=min(n-1, pos+d[pos]*a[pos]);
	int nb=get(pos);
	for (int i=pos+d[pos]; i<k*start+k && i<=end; i+=d[pos]) {
		block[i/k][i%k]+=nb;
		mod(block[i/k][i%k]);
	}
	return solveboth(nb, pos, start, end);
}

void solve() {
	cin >> n;
	a.resize(n), d.resize(n);
	for (int i=0; i<n; i++) cin >> d[i] >> a[i];
	build();
	int ans=0;
	for (int i=0; i<n; i++) ans=mod(ans+update(i));
	cout << ans << endl;
}

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