Submission #1052912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052912		vjudge1	Trains (BOI24_trains)	C++17	42 / 100	412 ms	288040 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int mod = 1'000'000'007;
const int SQ = 300, N = 100'000 + 5;
vector<int> chains[SQ][SQ];
int n, d[N], x[N], cnt[N], tnt[N][SQ];

int main()
{
  cin >> n;
  for(int i = 1; i <= n; i ++)
    cin >> d[i] >> x[i];

  for(int i = n; i >= 1; i --)
      for(int j = 1; j < SQ; j++)
	chains[j][i % j].push_back(i);

  cnt[1] = 1;
  int ans = 0;

  for(int i = 1; i <= n; i ++)
    {
      for(int j = 1; j < SQ; j++)
	cnt[i] = (cnt[i] + tnt[i][j]) % mod;
      ans = (ans + cnt[i]) % mod;

      for(int j = 1; j < SQ; j++)
	{
	  chains[j][i % j].pop_back();
	  if(chains[j][i % j].size())
	    tnt[i + j][j] = (tnt[i + j][j] + tnt[i][j]);
	}
      
      if(d[i] == 0) continue;

      if(d[i] >= SQ)
	{
	  for(int k = i + d[i]; k <= n; k += d[i])
	    cnt[k] = (cnt[i] + cnt[k]) % mod;
	}
      else
	{
	  x[i] = min(x[i], (n - i) / d[i]) + 1;
	  if(chains[d[i]][i % d[i]].size())
	    tnt[i + d[i]][d[i]] = (tnt[i + d[i]][d[i]] + cnt[i]) % mod;
	  if(x[i] * d[i] + i <= n)
	    tnt[x[i] * d[i] + i][d[i]] = (tnt[x[i] * d[i] + i][d[i]] + mod - cnt[i]) % mod;
	}
    }
  
  cout << ans << endl;
  return 0;
}

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