Submission #1097217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097217		duckindog	Trains (BOI24_trains)	C++17	37 / 100	47 ms	2908 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10,
          M = 1'000'000'007;
int n;
int d[N], x[N];

void add(int& x, const int& y) { 
  x += y;
  if (x >= M) x -= M;
};
namespace sub2 { 
  int f[N];
  void solve() { 
    for (int i = 1; i <= n; ++i) { 
      auto& ret = f[i];
      if (i == 1) ret = 1;

      if (!d[i]) continue;
      for (int j = 1; j <= x[i]; ++j) { 
        int t = i + j * d[i];
        if (t > n) break;
        
        add(f[t], ret);
      }
    }

    int answer = 0;
    for (int i = 1; i <= n; ++i) add(answer, f[i]);

    cout << answer << "\n";
  }
}

namespace sub3 { 
  int bit[N];
  void upd(int i, int x) { 
    for (; i <= n; i += i & -i) add(bit[i], x);
  }
  int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) add(ret, bit[i]);
    return ret;
  }

  void solve() { 
    upd(1, 1);  upd(2, -1);  
    for (int i = 1; i <= n; ++i) { 
      int ret = que(i);
      
      upd(i + 1, ret);
      upd(i + x[i] * d[i] + 1, M - ret);
    }

    int answer = 0;
    for (int i = 1; i <= n; ++i) add(answer, que(i));

    cout << answer << "\n";
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

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

  if (n <= 10'000) { sub2::solve(); return 0; }
  if (all_of(d + 1, d + n + 1, [](const auto& a) { return a == 1; })) {
    sub3::solve();
    return 0;
  }
}

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