oj.uz

Submission #395890

# Submission time Handle Problem Language Result Execution time Memory
395890 2021-04-29T05:43:54 Z Cyanmond Boat (APIO16_boat) C++17
100 / 100
 1942 ms 4300 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4276 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4268 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4300 KB Output is correct
8 Correct 7 ms 4172 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 7 ms 4172 KB Output is correct
11 Correct 7 ms 4172 KB Output is correct
12 Correct 7 ms 4180 KB Output is correct
13 Correct 7 ms 4248 KB Output is correct
14 Correct 7 ms 4268 KB Output is correct
15 Correct 7 ms 4176 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 3 ms 972 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4276 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4268 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4300 KB Output is correct
8 Correct 7 ms 4172 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 7 ms 4172 KB Output is correct
11 Correct 7 ms 4172 KB Output is correct
12 Correct 7 ms 4180 KB Output is correct
13 Correct 7 ms 4248 KB Output is correct
14 Correct 7 ms 4268 KB Output is correct
15 Correct 7 ms 4176 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Correct 827 ms 3916 KB Output is correct
22 Correct 808 ms 3916 KB Output is correct
23 Correct 700 ms 3884 KB Output is correct
24 Correct 788 ms 3864 KB Output is correct
25 Correct 845 ms 3880 KB Output is correct
26 Correct 1658 ms 3788 KB Output is correct
27 Correct 1717 ms 3840 KB Output is correct
28 Correct 1677 ms 3788 KB Output is correct
29 Correct 1647 ms 3756 KB Output is correct
30 Correct 9 ms 4172 KB Output is correct
31 Correct 11 ms 4276 KB Output is correct
32 Correct 9 ms 4172 KB Output is correct
33 Correct 9 ms 4276 KB Output is correct
34 Correct 10 ms 4264 KB Output is correct
35 Correct 12 ms 4264 KB Output is correct
36 Correct 9 ms 4172 KB Output is correct
37 Correct 9 ms 4172 KB Output is correct
38 Correct 10 ms 4172 KB Output is correct

Subtask #3
27.0 / 27.0

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

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4172 KB Output is correct
2 Correct 8 ms 4276 KB Output is correct
3 Correct 8 ms 4172 KB Output is correct
4 Correct 8 ms 4268 KB Output is correct
5 Correct 8 ms 4172 KB Output is correct
6 Correct 7 ms 4172 KB Output is correct
7 Correct 8 ms 4300 KB Output is correct
8 Correct 7 ms 4172 KB Output is correct
9 Correct 8 ms 4172 KB Output is correct
10 Correct 7 ms 4172 KB Output is correct
11 Correct 7 ms 4172 KB Output is correct
12 Correct 7 ms 4180 KB Output is correct
13 Correct 7 ms 4248 KB Output is correct
14 Correct 7 ms 4268 KB Output is correct
15 Correct 7 ms 4176 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 972 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Correct 827 ms 3916 KB Output is correct
22 Correct 808 ms 3916 KB Output is correct
23 Correct 700 ms 3884 KB Output is correct
24 Correct 788 ms 3864 KB Output is correct
25 Correct 845 ms 3880 KB Output is correct
26 Correct 1658 ms 3788 KB Output is correct
27 Correct 1717 ms 3840 KB Output is correct
28 Correct 1677 ms 3788 KB Output is correct
29 Correct 1647 ms 3756 KB Output is correct
30 Correct 9 ms 4172 KB Output is correct
31 Correct 11 ms 4276 KB Output is correct
32 Correct 9 ms 4172 KB Output is correct
33 Correct 9 ms 4276 KB Output is correct
34 Correct 10 ms 4264 KB Output is correct
35 Correct 12 ms 4264 KB Output is correct
36 Correct 9 ms 4172 KB Output is correct
37 Correct 9 ms 4172 KB Output is correct
38 Correct 10 ms 4172 KB Output is correct
39 Correct 6 ms 332 KB Output is correct
40 Correct 5 ms 420 KB Output is correct
41 Correct 6 ms 460 KB Output is correct
42 Correct 6 ms 460 KB Output is correct
43 Correct 7 ms 460 KB Output is correct
44 Correct 13 ms 424 KB Output is correct
45 Correct 13 ms 460 KB Output is correct
46 Correct 14 ms 464 KB Output is correct
47 Correct 13 ms 460 KB Output is correct
48 Correct 14 ms 460 KB Output is correct
49 Correct 7 ms 460 KB Output is correct
50 Correct 5 ms 416 KB Output is correct
51 Correct 6 ms 460 KB Output is correct
52 Correct 6 ms 460 KB Output is correct
53 Correct 7 ms 424 KB Output is correct
54 Correct 5 ms 332 KB Output is correct
55 Correct 4 ms 332 KB Output is correct
56 Correct 5 ms 296 KB Output is correct
57 Correct 4 ms 332 KB Output is correct
58 Correct 5 ms 332 KB Output is correct
59 Correct 895 ms 4256 KB Output is correct
60 Correct 803 ms 4264 KB Output is correct
61 Correct 774 ms 4260 KB Output is correct
62 Correct 907 ms 4276 KB Output is correct
63 Correct 862 ms 4272 KB Output is correct
64 Correct 1921 ms 4260 KB Output is correct
65 Correct 1918 ms 4256 KB Output is correct
66 Correct 1936 ms 4256 KB Output is correct
67 Correct 1901 ms 4260 KB Output is correct
68 Correct 1942 ms 4256 KB Output is correct
69 Correct 719 ms 4260 KB Output is correct
70 Correct 727 ms 4264 KB Output is correct
71 Correct 756 ms 4292 KB Output is correct
72 Correct 774 ms 4272 KB Output is correct
73 Correct 809 ms 4256 KB Output is correct
74 Correct 198 ms 1032 KB Output is correct
75 Correct 179 ms 972 KB Output is correct
76 Correct 191 ms 976 KB Output is correct
77 Correct 189 ms 1052 KB Output is correct
78 Correct 198 ms 972 KB Output is correct