oj.uz

Submission #801813

# Submission time Handle Problem Language Result Execution time Memory
801813 2023-08-02T07:51:30 Z peijar Boat (APIO16_boat) C++17
36 / 100
 2000 ms 2516 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <const int32_t MOD> struct ModInt {
  int32_t x;
  ModInt() : x(0) {}
  ModInt(long long u) : x(u % MOD) {
    if (x < 0)
      x += MOD;
  }
  friend bool operator==(const ModInt &a, const ModInt &b) {
    return a.x == b.x;
  }
  friend bool operator!=(const ModInt &a, const ModInt &b) {
    return a.x != b.x;
  }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.x < b.x; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.x > b.x; }
  friend bool operator<=(const ModInt &a, const ModInt &b) {
    return a.x <= b.x;
  }
  friend bool operator>=(const ModInt &a, const ModInt &b) {
    return a.x >= b.x;
  }
  static ModInt sign(long long k) {
    return ((k & 1) ? ModInt(MOD - 1) : ModInt(1));
  }

  ModInt &operator+=(const ModInt &m) {
    x += m.x;
    if (x >= MOD)
      x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &m) {
    x -= m.x;
    if (x < 0LL)
      x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &m) {
    x = (1LL * x * m.x) % MOD;
    return *this;
  }

  friend ModInt operator-(const ModInt &a) {
    ModInt res(a);
    if (res.x)
      res.x = MOD - res.x;
    return res;
  }
  friend ModInt operator+(const ModInt &a, const ModInt &b) {
    return ModInt(a) += ModInt(b);
  }
  friend ModInt operator-(const ModInt &a, const ModInt &b) {
    return ModInt(a) -= ModInt(b);
  }
  friend ModInt operator*(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b);
  }

  static long long fp(long long u, long long k) {
    long long res = 1LL;
    while (k > 0LL) {
      if (k & 1LL)
        res = (res * u) % MOD;
      u = (u * u) % MOD;
      k /= 2LL;
    }
    return res;
  }

  static constexpr int mod() { return MOD; }

  ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
  ModInt inv() {
    assert(x);
    return ModInt(fp(x, MOD - 2));
  }
  ModInt &operator/=(const ModInt &m) { return *this *= ModInt(m).inv(); }
  friend ModInt operator/(const ModInt &a, const ModInt &b) {
    return ModInt(a) *= ModInt(b).inv();
  }

  friend ostream &operator<<(ostream &out, const ModInt &a) {
    return out << a.x;
  }
  friend istream &operator>>(istream &in, ModInt &a) { return in >> a.x; }
  friend string to_string(ModInt u) { return to_string(u.x); }
};

const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;

const int MAXN = 1e5;
Mint fact[MAXN], invFact[MAXN];

void initFact() {
  fact[0] = 1;
  for (int i = 1; i < MAXN; ++i)
    fact[i] = i * fact[i - 1];
  invFact[MAXN - 1] = fact[MAXN - 1].inv();
  for (int i = MAXN - 1; i; --i)
    invFact[i - 1] = invFact[i] * i;
}

map<pair<int, int>, Mint> cache;

Mint binom(int n, int k) {
  if (k < 0 or k > n)
    return 0;
  if (n < MAXN)
    return fact[n] * invFact[k] * invFact[n - k];
  if (cache.count({n, k}))
    return cache[{n, k}];

  Mint ret = 1;
  for (int i = n; i > n - k; --i)
    ret *= i;
  ret *= invFact[k];
  return cache[{n, k}] = ret;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  initFact();

  int nbEcoles;
  cin >> nbEcoles;

  map<int, vector<int>> events;

  for (int iEcole = 0; iEcole < nbEcoles; ++iEcole) {
    int lo, up;
    cin >> lo >> up;
    events[lo - 1].push_back(-1);
    events[lo].push_back(iEcole);
    events[up].push_back(-1);
    events[1 + up].push_back(iEcole);
  }
  vector<Mint> dp(nbEcoles);
  vector<Mint> prefDp(nbEcoles + 1);
  set<int> on;
  int prev = 0;
  map<tuple<int, int, int>, Mint> cacheCalc;
  auto calc = [&](int szInt, int cntMiddle, bool midDiff) {
    if (cacheCalc.count({szInt, cntMiddle, midDiff}))
      return cacheCalc[{szInt, cntMiddle, midDiff}];
    Mint ret = 0;
    for (int takeMiddle = 0; takeMiddle <= cntMiddle; ++takeMiddle)
      ret +=
          binom(szInt, takeMiddle + 1 + midDiff) * binom(cntMiddle, takeMiddle);
    return cacheCalc[{szInt, cntMiddle, midDiff}] = ret;
  };
  for (auto [timeStamp, toUpdate] : events) {
    for (int x : toUpdate) {
      if (x == -1)
        continue;
      if (on.count(x))
        on.erase(x);
      else
        on.insert(x);
    }
    int lo = prev + 1, up = timeStamp;
    if (lo > up)
      continue;
    vector<int> vec(on.begin(), on.end());
    assert(is_sorted(vec.begin(), vec.end()));
    vector<Mint> nxtDp(on.size());
    for (int fst = 0; fst < (int)on.size(); ++fst)
      for (int lst = fst; lst < (int)on.size(); ++lst) {
        int middle = max(0LL, lst - fst - 1);
        Mint choixAvant = 1 + prefDp[vec[fst]];
        Mint choixMiddle = calc(up - lo + 1, middle, fst != lst);
        nxtDp[lst] += choixMiddle * choixAvant;
      }
    for (int i = 0; i < (int)vec.size(); ++i)
      dp[vec[i]] += nxtDp[i];
    for (int i = 0; i < nbEcoles; ++i)
      prefDp[i + 1] = prefDp[i] + dp[i];
    dbg(lo, up, on, dp);
    prev = up;
  }
  cout << accumulate(dp.begin(), dp.end(), Mint(0)) << endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 3 ms 1236 KB Output is correct
16 Correct 2 ms 1108 KB Output is correct
17 Correct 2 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 2 ms 1108 KB Output is correct
21 Correct 1679 ms 1876 KB Output is correct
22 Correct 1578 ms 2020 KB Output is correct
23 Correct 1381 ms 1736 KB Output is correct
24 Correct 1609 ms 1808 KB Output is correct
25 Correct 1601 ms 1840 KB Output is correct
26 Execution timed out 2066 ms 2080 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1996 KB Output is correct
2 Correct 21 ms 1828 KB Output is correct
3 Correct 25 ms 1976 KB Output is correct
4 Correct 27 ms 1952 KB Output is correct
5 Correct 30 ms 2048 KB Output is correct
6 Correct 70 ms 2440 KB Output is correct
7 Correct 63 ms 2516 KB Output is correct
8 Correct 62 ms 2476 KB Output is correct
9 Correct 66 ms 2436 KB Output is correct
10 Correct 63 ms 2412 KB Output is correct
11 Correct 34 ms 2132 KB Output is correct
12 Correct 21 ms 1876 KB Output is correct
13 Correct 26 ms 2052 KB Output is correct
14 Correct 25 ms 1992 KB Output is correct
15 Correct 29 ms 2032 KB Output is correct
16 Correct 14 ms 1456 KB Output is correct
17 Correct 14 ms 1492 KB Output is correct
18 Correct 13 ms 1520 KB Output is correct
19 Correct 12 ms 1432 KB Output is correct
20 Correct 15 ms 1576 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 3 ms 1236 KB Output is correct
16 Correct 2 ms 1108 KB Output is correct
17 Correct 2 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 2 ms 1108 KB Output is correct
21 Correct 1679 ms 1876 KB Output is correct
22 Correct 1578 ms 2020 KB Output is correct
23 Correct 1381 ms 1736 KB Output is correct
24 Correct 1609 ms 1808 KB Output is correct
25 Correct 1601 ms 1840 KB Output is correct
26 Execution timed out 2066 ms 2080 KB Time limit exceeded
27 Halted 0 ms 0 KB -