oj.uz

Submission #801967

# Submission time Handle Problem Language Result Execution time Memory
801967 2023-08-02T08:46:58 Z peijar Boat (APIO16_boat) C++17
27 / 100
 2000 ms 3812 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;

  vector<array<Mint, 2>> precalc(nbEcoles + 1);

  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) {
    Mint ret = 0;
    for (int takeMiddle = 0; takeMiddle <= cntMiddle; ++takeMiddle)
      ret +=
          binom(szInt, takeMiddle + 1 + midDiff) * binom(cntMiddle, takeMiddle);
    precalc[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;
    for (int cntMiddle = 0; cntMiddle <= nbEcoles; ++cntMiddle)
      for (int midDiff : {0, 1})
        calc(up - lo + 1, cntMiddle, midDiff);
    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 = precalc[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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 3812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 3812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 2400 KB Output is correct
2 Correct 171 ms 2264 KB Output is correct
3 Correct 172 ms 2316 KB Output is correct
4 Correct 178 ms 2348 KB Output is correct
5 Correct 192 ms 2352 KB Output is correct
6 Correct 202 ms 2400 KB Output is correct
7 Correct 173 ms 2276 KB Output is correct
8 Correct 169 ms 2428 KB Output is correct
9 Correct 173 ms 2344 KB Output is correct
10 Correct 174 ms 2376 KB Output is correct
11 Correct 173 ms 2360 KB Output is correct
12 Correct 170 ms 2328 KB Output is correct
13 Correct 170 ms 2380 KB Output is correct
14 Correct 169 ms 2324 KB Output is correct
15 Correct 180 ms 2424 KB Output is correct
16 Correct 77 ms 1616 KB Output is correct
17 Correct 73 ms 1616 KB Output is correct
18 Correct 77 ms 1596 KB Output is correct
19 Correct 75 ms 1656 KB Output is correct
20 Correct 79 ms 1572 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 3812 KB Time limit exceeded
2 Halted 0 ms 0 KB -