Submission #395890

#	Time	Username	Problem	Language	Result	Execution time	Memory
395890		Cyanmond	Boat (APIO16_boat)	C++17	100 / 100	1942 ms	4300 KiB

boat

#pragma region template
#include "bits/stdc++.h"

using llint = long long;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T>
T read() {
  T ret; std::cin >> ret;
  return ret;
}

template <class T>
auto mk_vec(const int n, const T value) { return std::vector(n, value); }
template <class... Args>
auto mk_vec(const int n, Args... args) { return std::vector(n, mk_vec(args...)); }

template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class range {
  struct range_iterator {
    T itr;
    constexpr range_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator != (const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };
  const range_iterator first, last;
public:
  constexpr range(const T first_, const T last_) noexcept : first(first_), last(last_) {}
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }
};

template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class revrange {
  struct revrange_iterator {
    T itr;
    constexpr revrange_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator != (const revrange_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };
  const revrange_iterator first, last;
public:
  constexpr revrange(const T first_, const T last_) noexcept : first(first_), last(last_ - 1) {}
  constexpr revrange_iterator begin() const noexcept { return first; }
  constexpr revrange_iterator end() const noexcept { return last; }
};

template <class F>
class rec_lambda {
  F f;
public:
  constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};
#pragma endregion

namespace mtl {
  template <class T, class U>
  constexpr T Pow(T A, U B) noexcept {
    T res = 1;
    while (B) {
      if (B & 1) { res *= A; }
      A *= A; B >>= 1;
    }
    return res;
  }

  template <class M = int>
  constexpr long long modpow(long long A, long long B, const M MOD = 1000000007) noexcept {
    A %= MOD;
    long long res = 1;
    while (B > 0) {
      if (B & 1) { res *= A; res %= MOD; }
      A *= A; A %= MOD;
      B >>= 1;
    }
    return res;
  }

  template <class T, class M = int>
  constexpr T inverse(T A, const M MOD = 1000000007) noexcept {
    T B = MOD, U = 1, V = 0;
    while (B) {
      T t = A / B;
      A -= t * B; std::swap(A, B);
      U -= t * V; std::swap(U, V);
    }
    U %= MOD;
    return U < 0 ? U += MOD, U : U;
  }

  inline std::tuple<long long, long long, long long> extgcd(const long long a, const long long b) {
    if (b == 0) return { a,1,0 };
    long long g, x, y;
    std::tie(g, x, y) = extgcd(b, a % b);
    return std::make_tuple(g, y, x - a / b * y);
  }

  inline std::pair<long long, long long> Chinese_Rem(const std::vector<long long>& b, const std::vector<long long>& m) {
    long long r = 0, M = 1;
    for (int i = 0; i < (int)b.size(); ++i) {
      long long p, q, d;
      std::tie(d, p, q) = extgcd(M, m[i]);
      if ((b[i] - r) % d != 0) return std::make_pair(0, -1);
      long long tmp = (b[i] - r) / d * p % (m[i] / d);
      r += M * tmp;
      M *= m[i] / d;
    }
    return std::make_pair((r % M + M) % M, M);
  }
}

constexpr llint mod = 1000000007ll;

int main() {
  const int N = read<int>() + 1;
  std::vector<int> A(N), B(N);
  A[0] = 0; B[0] = 1;
  for (const int i : range(1, N)) {
    std::cin >> A[i] >> B[i];
    ++B[i];
  }

  std::vector<llint> press;
  press.reserve(2 * N);
  for (const int i : range(0, N)) {
    press.emplace_back(A[i]);
    press.emplace_back(B[i]);
  }
  std::sort(press.begin(), press.end());
  press.erase(std::unique(press.begin(), press.end()), press.end());
  int M = int(press.size());
  for (const int i : range(0, N)) {
    A[i] = int(std::lower_bound(press.begin(), press.end(), A[i]) - press.begin() + 1);
    B[i] = int(std::lower_bound(press.begin(), press.end(), B[i]) - press.begin() + 1);
  }

  auto DP = mk_vec(N + 1, M, 0ll);
  // DP[i][j]
  // last (index, value) = (i, j)
  // cumulative sum
  std::fill(DP[0].begin(), DP[0].end(), 1ll);
  for (const int i : range(1, N)) {
    for (const int j : range(A[i], B[i])) {
      llint width = press[j] - press[j - 1];
      auto S = width, X = 1ll;
      for (const int k : revrange(i - 1, 0)) {
        // from DP[k] to DP[i][j]
        DP[i][j] = (DP[i][j] + DP[k][j - 1] * width) % mod;
        if (A[k] <= j and j < B[k]) {
          width = width * ++S % mod * mtl::inverse(++X) % mod;
          // count only monotonically increasing
        }
      }
    }

    for (const int j : range(1, M)) DP[i][j] = (DP[i][j] + DP[i][j - 1]) % mod;
  }
  const auto ans = std::accumulate(DP.begin() + 1, DP.end(),
    0ll, [M](llint& ac, std::vector<llint>& b)->llint {return (ac + b[M - 1]) % mod; });
  std::cout << ans << std::endl;
}

Compilation message (stderr)

boat.cpp:1: warning: ignoring #pragma region template [-Wunknown-pragmas]
    1 | #pragma region template
      | 
boat.cpp:65: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
   65 | #pragma endregion
      |

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42