oj.uz

Submission #942928

# Submission time Handle Problem Language Result Execution time Memory
942928 2024-03-11T07:03:06 Z ventusliberum A Huge Tower (CEOI10_tower) C++17
100 / 100
 93 ms 8788 KB 
/**
 *    title:   Huge Tower
**/
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define overload(a, b, c, d, ...) d
#define rep0(n) for (int _ = 0; _ < (n); _++)
#define rep1(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define rep(...) overload(__VA_ARGS__, rep2, rep1, rep0)(__VA_ARGS__)
#define rrep1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrep2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
template <class T> inline bool chmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
template <class T> inline bool chmin(T &a, T b) { return (b < a ? a = b, 1 : 0); }
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

template <class T>
constexpr T power(T a, long long b) {
  T res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

template <int mod>
struct ModInt {
  int x;
  constexpr ModInt() : x{} {}
  constexpr ModInt(long long x) : x{norm(x % mod)} {}

  constexpr int norm(int x) const {
    if (x < 0) {
      x += mod;
    }
    if (x >= mod) {
      x -= mod;
    }
    return x;
  }
  constexpr int val() const {
    return x;
  }
  constexpr ModInt inv() const {
    assert(x != 0);
    return power(*this, mod - 2);
  }
  explicit constexpr operator int() const {
    return x;
  }
  constexpr ModInt operator-() const {
    ModInt res;
    res.x = norm(mod - x);
    return res;
  }
  constexpr ModInt& operator+=(ModInt rhs) {
    x = norm(x + rhs.x);
    return *this;
  }
  constexpr ModInt& operator-=(ModInt rhs) {
    x = norm(x - rhs.x);
    return *this;
  }
  constexpr ModInt& operator++() {
    return *this += 1;
  }
  constexpr ModInt& operator--() {
    return *this -= 1;
  }
  constexpr ModInt operator++(int) {
    ModInt res(*this);
    *this += 1;
    return res;
  }
  constexpr ModInt operator--(int) {
    ModInt res(*this);
    *this -= 1;
    return res;
  }
  constexpr ModInt& operator*=(ModInt rhs) {
    x = 1LL * x * rhs.x % mod;
    return *this;
  }
  constexpr ModInt& operator/=(ModInt rhs) {
    return *this *= rhs.inv();
  }
  friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res += rhs;
    return res;
  }
  friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res -= rhs;
    return res;
  }
  friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res *= rhs;
    return res;
  }
  friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res /= rhs;
    return res;
  }
  friend constexpr std::istream& operator>>(std::istream& is, ModInt& a) {
    long long v{};
    is >> v;
    a = ModInt(v);
    return is;
  }
  friend constexpr std::ostream& operator<<(std::ostream& os, const ModInt& a) {
    return os << a.val();
  }
  friend constexpr bool operator==(ModInt lhs, ModInt rhs) {
    return lhs.val() == rhs.val();
  }
  friend constexpr bool operator!=(ModInt lhs, ModInt rhs) {
    return lhs.val() != rhs.val();
  }
};

template <int num, int mod>
constexpr ModInt<mod> CInv = ModInt<mod>(num).inv();

constexpr int mod = 1000000009;
using mint = ModInt<mod>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, d;
  cin >> n >> d;
  vector<int> a(n);
  rep(i, n) {
    cin >> a[i];
  }
  sort(all(a));
  mint ans = 1;
  int j = 0;
  rep(i, 1, n) {
    while (a[j] + d < a[i]) j++;
    ans *= (i - j + 1);
  }
  cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1116 KB Output is correct
2 Correct 7 ms 1116 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3668 KB Output is correct
2 Correct 39 ms 3732 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8788 KB Output is correct
2 Correct 93 ms 8276 KB Output is correct