Submission #1232590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232590		asdfgrace	Trains (BOI24_trains)	C++20	100 / 100	121 ms	7240 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) {cerr << y << ' ';} cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
dp[i] = # of unique paths if you get on the train at i
it's gonna be the sum of all unique paths of stuff that is a multiple of d[i] after i
as long as they are stops
if there are less than sqrt(n) stops, you can add all of them
if d[i] = 1 you could maintain a single suffix sum
if there are more than sqrt(n) stops:
???
there are still o(n) combinations of an interval & a mod, so you can't maintain all of them
actually every element only fits o(sqrt(n)) of them
so just maintain a running suffix thing of these
ok
now we modify them so we can query suffixes
maybe you can make the sum 0 when it's about to "start"
or just record the sum at the index where it's important
*/

const long long mod = 1e9 + 7;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int> d(n), x(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i] >> x[i];
  }
  int s = sqrt(n);
  vector<vector<long long>> md(s + 1);
  for (int i = 1; i <= s; i++) {
    md[i].resize(i, 0);
  }
  vector<vector<int>> at(n + 1);
  for (int i = 0; i < n; i++) {
    if (d[i] > 0 && d[i] <= s && x[i] <= n) {
      int ind = min(n - 1, i + d[i] * x[i]);
      at[ind + 1].push_back(i);
    }
  }
  vector<long long> bgn(n, 0);
  vector<long long> dp(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    dp[i] = 1;
    if (d[i] > s) {
      for (int j = i + d[i]; j < n && (j - i) / d[i] <= x[i]; j += d[i]) {
        dp[i] += dp[j]; dp[i] %= mod;
      }
    } else if (d[i] > 0) {
      dp[i] += md[d[i]][i % d[i]]; dp[i] %= mod;
      dp[i] += mod - bgn[i]; dp[i] %= mod;
    }
    for (int j = 1; j <= s; j++) {
      md[j][i % j] += dp[i]; md[j][i % j] %= mod;
    }
    for (auto ind : at[i]) {
      bgn[ind] = md[d[ind]][ind % d[ind]];
    }
  }
  cout << dp[0] << '\n';
}

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