fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. // const int MOD = 1e9 + 7; // 998244353
  52. const int MOD = 1e6 + 3;
  53. const int inf = 1e9;
  54. const ll INF = 1e18; // MASK(63) - 1
  55. const int N = 4e5;
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58. ll random(const ll &L, const ll &R) {
  59.     return uniform_int_distribution<ll> (L, R) (rng);
  60. }
  61.  
  62. int n, a[N + 5], m, lim;
  63.  
  64. const int LIM = 8e5;
  65. ll fact[LIM + 5], invfact[LIM + 5], invNum[N + 5];
  66.  
  67. ll powmod(ll a, ll b) {
  68.     ll res = 1;
  69.     while (b) {
  70.         if (b & 1) res = res * a % MOD;
  71.         a = a * a % MOD;
  72.         b >>= 1;
  73.     }
  74.     return res;
  75. }
  76.  
  77. ll C(ll n, ll k) {
  78.     if (k < 0 || k > n) return 0;
  79.     return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
  80. }
  81.  
  82. void build() {
  83.     fact[0] = 1;
  84.     forw (i, 1, LIM) fact[i] = fact[i - 1] * i % MOD;
  85.  
  86.     invfact[LIM] = powmod(fact[LIM], MOD - 2);
  87.     fors (i, LIM - 1, 0) invfact[i] = invfact[i + 1] * (i + 1) % MOD;
  88.  
  89.     invNum[1] = 1;
  90.     forw (i, 2, N + 1) invNum[i] = MOD - MOD / i * invNum[MOD % i] % MOD;
  91. }
  92.  
  93. ll catalan(ll n) {
  94.     return C(2 * n, n) * invNum[n + 1] % MOD;
  95. }
  96.  
  97. const int N4 = 4e3;
  98. ll dp[N4 + 5];
  99. void sub4() {
  100.     dp[0] = 1;
  101.     for (int i = 2; i <= lim; i += 2) {
  102.         for (int j = i - 1; j >= 1 && a[j] + m >= a[i]; j -= 2) {
  103.             (dp[i] += dp[j - 1] * catalan((i - j - 1) / 2)) %= MOD;
  104.         }
  105.     }
  106.     cout << dp[lim] << endl;
  107. }
  108.  
  109. void sub5() {
  110.  
  111. }
  112.  
  113. void solve() {
  114.     cin >> n >> m;
  115.     lim = n << 1;
  116.     forw (i, 1, lim) cin >> a[i];
  117.     build();
  118.     if (n <= 2e3) sub4();
  119.     else sub5();
  120. }
  121.  
  122. signed main() {
  123.     ios::sync_with_stdio(false), cin.tie(nullptr);
  124.     srand(time(NULL));
  125.     #define name "test"
  126.     /*
  127.     if (fopen(name".INP", "r")) {
  128.         freopen(name".INP", "r", stdin);
  129.         freopen(name".OUT", "w", stdout);
  130.     }
  131.     */
  132.     bool testCase = false;
  133.     int numTest = 1;
  134. //    cin >> numTest;
  135.     forw (i, 1, numTest) {
  136.         if (testCase) cout << "Case " << i << ": ";
  137.         solve();
  138.     }
  139.     return 0;
  140. }
Success #stdin #stdout 0.02s 19636KB
comments (?)
stdin
copy 
3 6
1 2 3 7 9 10
stdout
copy 
2
https://ideone.com/iE6msI
language:
C++14 (gcc 8.3)
created:
23 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!