oj.uz

Submission #408644

# Submission time Handle Problem Language Result Execution time Memory
408644 2021-05-19T12:05:10 Z tranxuanbach Boat (APIO16_boat) C++17
36 / 100
 717 ms 6376 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}


template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

const int N = 5e2 + 5, mod = 1e9 + 7;

int n;
pii a[N];

Mint invfac[N], C[N][N];

void init_C(){
    invfac[0] = 1;
    For(i, 1, N){
        invfac[i] = invfac[i - 1] / i;
    }
    C[0][0] = 1;
    For(i, 1, N){
        ForE(j, 0, i){
            C[i][j] = C[i - 1][j] + (j ? C[i - 1][j - 1] : 0);
        }
    }
}

int m;
vpii ranges;

void coordinate_compress(){
    vpii vcac;
    ForE(i, 1, n){
        vcac.emplace_back(a[i].fi, 0);
        vcac.emplace_back(a[i].se + 1, 0);
    }
    sort(bend(vcac));
    ForE(i, 1, n){
        For(j, 0, isz(vcac)){
            if (a[i].fi <= vcac[j].fi and vcac[j].fi <= a[i].se){
                vcac[j].se = 1;
            }
        }
    }
    ranges.emplace_back(-1, -1);
    For(j, 0, isz(vcac) - 1){
        if (vcac[j].se){
            ranges.emplace_back(vcac[j].fi, vcac[j + 1].fi - 1);
        }
    }
    ForE(i, 1, n){
        a[i].fi = lower_bound(bend(ranges), make_pair(a[i].fi, -1)) - ranges.begin();
        a[i].se = (--lower_bound(bend(ranges), make_pair(a[i].se + 1, -1))) - ranges.begin();
    }
    m = isz(ranges) - 1;
}

Mint Crange[2 * N][N];

void init_Crange(){
    ForE(i, 1, m){
        int len = ranges[i].se - ranges[i].fi + 1;
        Mint ans = 1;
        ForE(j, 0, n){
            if (j > len){
                Crange[i][j] = 0;
                continue;
            }
            Crange[i][j] = ans;
            ans /= j + 1; ans *= len - j;
        }
    }
}

Mint calchoose[N][2 * N];

void init_calchoose(){
    ForE(i, 1, n){
        ForE(j, 1, m){
            For(neg1, 0, i){
                calchoose[i][j] += C[i - 1][neg1] * Crange[j][i - neg1];
            }
        }
    }
}

Mint dp[N][N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    init_C();
    cin >> n;
    ForE(i, 1, n){
        cin >> a[i].fi >> a[i].se;
    }
    coordinate_compress();
    init_Crange();
    init_calchoose();
    ForE(i, 0, n){
        dp[i][0] = 1;
    }
    ForE(j, 1, m){
        dp[0][j] = 1;
    }
    ForE(i, 1, n){
        ForE(j, 1, m){
            dp[i][j] = dp[i][j - 1];
            int len = 0;
            FordE(ti, i, 1){
                if (a[ti].fi > j or a[ti].se < j){
                    continue;
                }
                len++;
                dp[i][j] += calchoose[len][j] * dp[ti - 1][j - 1];
            }
        }
    }
    cout << dp[n][m] - 1 << endl;
}

/*
Tim so day so A = (A_1, A_2, ..., A_n) thoa man dieu kien sau:
- A_i = -1 hoac a_i <= A_i <= b_i
- Neu i < j, A_i != -1 va A_j != -1 thi A_i < A_j.

nen so thanh n doan, sau do thi
dp[i][j] la so cach de chon i so dau va moi so <= j (sau khi nen).
dp[i][j] = dp[i][j - 1] + (so cach chon (i - i' + 1) so co gia tri = j hoac -1 sau khi nen, so dau phai bang j) * dp[i' - 1][j - 1]
so cach chon tren: goi len = i - i'.
so cach = \sum_{neg1 = 0}^{len} C(len, neg1) * C(range(j), len + 1 - neg1)
==================================================+
INPUT:                                            |
--------------------------------------------------|
2
1 2
2 3
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5208 KB Output is correct
2 Correct 247 ms 5376 KB Output is correct
3 Correct 245 ms 5188 KB Output is correct
4 Correct 248 ms 5288 KB Output is correct
5 Correct 248 ms 5432 KB Output is correct
6 Correct 214 ms 5248 KB Output is correct
7 Correct 217 ms 5288 KB Output is correct
8 Correct 218 ms 5316 KB Output is correct
9 Correct 219 ms 5288 KB Output is correct
10 Correct 217 ms 5296 KB Output is correct
11 Correct 215 ms 5316 KB Output is correct
12 Correct 220 ms 5288 KB Output is correct
13 Correct 212 ms 5288 KB Output is correct
14 Correct 212 ms 5192 KB Output is correct
15 Correct 213 ms 5316 KB Output is correct
16 Correct 250 ms 5388 KB Output is correct
17 Correct 247 ms 5188 KB Output is correct
18 Correct 287 ms 5288 KB Output is correct
19 Correct 255 ms 5308 KB Output is correct
20 Correct 252 ms 5276 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5208 KB Output is correct
2 Correct 247 ms 5376 KB Output is correct
3 Correct 245 ms 5188 KB Output is correct
4 Correct 248 ms 5288 KB Output is correct
5 Correct 248 ms 5432 KB Output is correct
6 Correct 214 ms 5248 KB Output is correct
7 Correct 217 ms 5288 KB Output is correct
8 Correct 218 ms 5316 KB Output is correct
9 Correct 219 ms 5288 KB Output is correct
10 Correct 217 ms 5296 KB Output is correct
11 Correct 215 ms 5316 KB Output is correct
12 Correct 220 ms 5288 KB Output is correct
13 Correct 212 ms 5288 KB Output is correct
14 Correct 212 ms 5192 KB Output is correct
15 Correct 213 ms 5316 KB Output is correct
16 Correct 250 ms 5388 KB Output is correct
17 Correct 247 ms 5188 KB Output is correct
18 Correct 287 ms 5288 KB Output is correct
19 Correct 255 ms 5308 KB Output is correct
20 Correct 252 ms 5276 KB Output is correct
21 Incorrect 717 ms 6376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2252 KB Output is correct
2 Correct 10 ms 2216 KB Output is correct
3 Correct 12 ms 2324 KB Output is correct
4 Correct 10 ms 2252 KB Output is correct
5 Correct 13 ms 2252 KB Output is correct
6 Correct 11 ms 2324 KB Output is correct
7 Correct 14 ms 2252 KB Output is correct
8 Correct 11 ms 2252 KB Output is correct
9 Correct 11 ms 2252 KB Output is correct
10 Correct 11 ms 2216 KB Output is correct
11 Correct 11 ms 2324 KB Output is correct
12 Correct 10 ms 2308 KB Output is correct
13 Correct 12 ms 2252 KB Output is correct
14 Correct 10 ms 2216 KB Output is correct
15 Correct 10 ms 2320 KB Output is correct
16 Correct 10 ms 2248 KB Output is correct
17 Correct 9 ms 2328 KB Output is correct
18 Correct 9 ms 2252 KB Output is correct
19 Correct 9 ms 2252 KB Output is correct
20 Correct 9 ms 2228 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5208 KB Output is correct
2 Correct 247 ms 5376 KB Output is correct
3 Correct 245 ms 5188 KB Output is correct
4 Correct 248 ms 5288 KB Output is correct
5 Correct 248 ms 5432 KB Output is correct
6 Correct 214 ms 5248 KB Output is correct
7 Correct 217 ms 5288 KB Output is correct
8 Correct 218 ms 5316 KB Output is correct
9 Correct 219 ms 5288 KB Output is correct
10 Correct 217 ms 5296 KB Output is correct
11 Correct 215 ms 5316 KB Output is correct
12 Correct 220 ms 5288 KB Output is correct
13 Correct 212 ms 5288 KB Output is correct
14 Correct 212 ms 5192 KB Output is correct
15 Correct 213 ms 5316 KB Output is correct
16 Correct 250 ms 5388 KB Output is correct
17 Correct 247 ms 5188 KB Output is correct
18 Correct 287 ms 5288 KB Output is correct
19 Correct 255 ms 5308 KB Output is correct
20 Correct 252 ms 5276 KB Output is correct
21 Incorrect 717 ms 6376 KB Output isn't correct
22 Halted 0 ms 0 KB -