oj.uz

Submission #262599

# Submission time Handle Problem Language Result Execution time Memory
262599 2020-08-13T05:04:45 Z KoD Boat (APIO16_boat) C++17
31 / 100
 114 ms 8144 KB 
/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>


template <class T, class U>
bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

template <class T, class U>
bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

/**
 * @title Chmin/Chmax
 */


class range {
public:
  class iterator {
  private:
    int64_t M_position;

  public:
    iterator(int64_t position) noexcept: M_position(position) { }
    void operator ++ () noexcept { ++M_position; }
    bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    int64_t operator * () const noexcept { return M_position; }

  };

  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    reverse_iterator(int64_t position) noexcept: M_position(position) { }
    void operator ++ () noexcept { --M_position; }
    bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    int64_t operator * () const noexcept { return M_position; }

  };
  
private:
  const iterator M_first, M_last;

public:
  range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  iterator begin() const noexcept { return M_first; }
  iterator end() const noexcept { return M_last; }
  reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 

};

/**
 * @title Range
 */

#include <type_traits>
#include <iterator>

template <class T>
class rev_impl {
public:
  using iterator = decltype(std::declval<T>().rbegin());

private:
  const iterator M_begin;
  const iterator M_end;

public:
  rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { }
  iterator begin() const noexcept { return M_begin; }
  iterator end() const noexcept { return M_end; }

};

template <class T>
rev_impl<T> rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */

#include <cstdint>

template <class Modulus>
class modular {
public:
  using value_type = uint32_t;
  using cover_type = uint64_t;
  static constexpr value_type mod() { return Modulus::value(); }

  template <class T>
  static value_type normalize(T value_) noexcept {
    if (value_ < 0) {
      value_ = -value_;
      value_ %= mod();
      if (value_ == 0) return 0;
      return mod() - value_;
    }
    return value_ % mod();
  }

private:
  value_type value;

public:
  modular() noexcept : value(0) { }
  template <class T>
  explicit modular(T value_) noexcept : value(normalize(value_)) { }
  template <class T>
  explicit operator T() const noexcept { return static_cast<T>(value); }

  value_type get() const noexcept { return value; }
  modular operator - () const noexcept { return modular(mod() - value); }
  modular operator ~ () const noexcept { return inverse(); }

  value_type &extract() noexcept { return value; }
  modular inverse() const noexcept { return power(mod() - 2); }
  modular power(cover_type exp) const noexcept {
    modular res(1), mult(*this);
    while (exp > 0) {
      if (exp & 1) res *= mult;
      mult *= mult;
      exp >>= 1;
    }
    return res;
  }

  modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; }
  modular& operator += (const modular &rhs) noexcept { 
    if ((value += rhs.value) >= mod()) value -= mod(); 
    return *this; 
  }

  modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; }
  modular& operator -= (const modular &rhs) noexcept { 
    if ((value += mod() - rhs.value) >= mod()) value -= mod(); 
    return *this; 
  }

  modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; }
  modular& operator *= (const modular &rhs) noexcept { 
    value = (cover_type) value * rhs.value % mod();
    return *this;
  }

  modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; }
  modular& operator /= (const modular &rhs) noexcept { return (*this) *= rhs.inverse(); }

  bool zero() const noexcept { return value == 0; }
  bool operator == (const modular &rhs) const noexcept { return value == rhs.value; }
  bool operator != (const modular &rhs) const noexcept { return value != rhs.value; }

  friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; }
  friend modular power(modular val, cover_type exp) noexcept { return val.power(exp); }
  friend modular inverse(modular val) noexcept { return val.inverse(); }

};

template <uint32_t Val>
struct modulus_impl { static constexpr uint32_t value() noexcept { return Val; } };
template <uint32_t Val>
using mint32_t = modular<modulus_impl<Val>>;

struct runtime_mod { static uint32_t &value() noexcept { static uint32_t val = 0; return val; } };
using rmint32_t = modular<runtime_mod>;

/**
 * @title Modint
 */


#include <cstddef>

size_t bit_ppc(const uint64_t x) {
  return __builtin_popcountll(x);
}

size_t bit_ctzr(const uint64_t x) {
  return x == 0 ? 64 : __builtin_ctzll(x);
}

size_t bit_ctzl(const uint64_t x) {
  return x == 0 ? 64 : __builtin_clzll(x);
}

size_t bit_width(const uint64_t x) { 
  return 64 - bit_ctzl(x);
}

uint64_t bit_msb(const uint64_t x) {
  return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1);
}

uint64_t bit_lsb(const uint64_t x) {
  return x & (-x);
}

uint64_t bit_cover(const uint64_t x) {
  return x == 0 ? 0 : bit_msb(2 * x - 1);
}

uint64_t bit_rev(uint64_t x) {
  x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
  x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
  x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
  x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
  x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
  x = (x >> 32) | (x << 32);
  return x;
}

/**
 * @title Bit Operations
 */


template <class T>
class fenwick_tree {
public:
  using value_type = T;
  using size_type = size_t;

private:
  std::vector<value_type> M_tree;

public:
  fenwick_tree() = default;
  explicit fenwick_tree(size_type size) { initialize(size); }

  void initialize(size_type size) {
    M_tree.assign(size + 1, value_type{});
  }

  void add(size_type index, const value_type& x) {
    ++index;
    while (index <= size()) {
      M_tree[index] += x;
      index += bit_lsb(index);
    }
  }

  value_type get(size_type index) const {
    ++index;
    value_type res{};
    while (index > 0) {
      res += M_tree[index];
      index -= bit_lsb(index);
    }
    return res;
  }
  value_type fold(size_type l, size_type r) const {
    if (l == 0 && r == 0) return value_type{};
    if (l == 0) return get(r - 1);
    return get(r - 1) - get(l - 1);
  }

  size_type size() const {
    return M_tree.size() - 1;
  }

};

/**
 * @title Fenwick Tree
 */

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

using m32 = mint32_t<1000000007>;

int main() {
  size_t N;
  std::cin >> N;
  std::vector<std::pair<i32, i32>> boat(N);
  i64 sum = 0;
  for (auto &p: boat) {
    std::cin >> p.first >> p.second;
    sum += p.second - p.first;
  }
  assert(sum <= 1000000);
  std::vector<i32> vec;
  vec.reserve(sum + 1);
  vec.push_back(0);
  for (auto p: boat) {
    for (auto i: range(p.first, p.second + 1)) {
      vec.push_back(i);
    }
  }
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  fenwick_tree<m32> dp(vec.size());
  dp.add(0, m32(1));
  for (auto p: boat) {
    i32 st = std::lower_bound(vec.begin(), vec.end(), p.first) - vec.begin();
    for (auto i: rev(range(st, st + p.second - p.first + 1))) {
      dp.add(i, dp.get(i - 1));
    }
  }
  std::cout << dp.get(dp.size() - 1) - m32(1) << '\n';
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 60 ms 7168 KB Output is correct
22 Correct 60 ms 7168 KB Output is correct
23 Correct 56 ms 6784 KB Output is correct
24 Correct 62 ms 7424 KB Output is correct
25 Correct 63 ms 7424 KB Output is correct
26 Correct 64 ms 7808 KB Output is correct
27 Correct 66 ms 7968 KB Output is correct
28 Correct 67 ms 7936 KB Output is correct
29 Correct 67 ms 8064 KB Output is correct
30 Correct 89 ms 8144 KB Output is correct
31 Correct 114 ms 7956 KB Output is correct
32 Correct 91 ms 8140 KB Output is correct
33 Correct 87 ms 7984 KB Output is correct
34 Correct 87 ms 7952 KB Output is correct
35 Correct 95 ms 7624 KB Output is correct
36 Correct 97 ms 7880 KB Output is correct
37 Correct 99 ms 7936 KB Output is correct
38 Correct 95 ms 7708 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 60 ms 7168 KB Output is correct
22 Correct 60 ms 7168 KB Output is correct
23 Correct 56 ms 6784 KB Output is correct
24 Correct 62 ms 7424 KB Output is correct
25 Correct 63 ms 7424 KB Output is correct
26 Correct 64 ms 7808 KB Output is correct
27 Correct 66 ms 7968 KB Output is correct
28 Correct 67 ms 7936 KB Output is correct
29 Correct 67 ms 8064 KB Output is correct
30 Correct 89 ms 8144 KB Output is correct
31 Correct 114 ms 7956 KB Output is correct
32 Correct 91 ms 8140 KB Output is correct
33 Correct 87 ms 7984 KB Output is correct
34 Correct 87 ms 7952 KB Output is correct
35 Correct 95 ms 7624 KB Output is correct
36 Correct 97 ms 7880 KB Output is correct
37 Correct 99 ms 7936 KB Output is correct
38 Correct 95 ms 7708 KB Output is correct
39 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -