oj.uz

Submission #801811

# Submission time Handle Problem Language Result Execution time Memory
801811 2023-08-02T07:50:26 Z peijar Boat (APIO16_boat) C++17
36 / 100
 2000 ms 9504 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 (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 4 ms 1240 KB Output is correct
3 Correct 3 ms 1240 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 4 ms 1240 KB Output is correct
7 Correct 4 ms 1244 KB Output is correct
8 Correct 3 ms 1196 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 4 ms 1244 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 3 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 3 ms 1116 KB Output is correct
18 Correct 2 ms 1112 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 3 ms 1236 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 4 ms 1240 KB Output is correct
3 Correct 3 ms 1240 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 4 ms 1240 KB Output is correct
7 Correct 4 ms 1244 KB Output is correct
8 Correct 3 ms 1196 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 4 ms 1244 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 3 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 3 ms 1116 KB Output is correct
18 Correct 2 ms 1112 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 1798 ms 4056 KB Output is correct
22 Correct 1645 ms 4016 KB Output is correct
23 Correct 1427 ms 3524 KB Output is correct
24 Correct 1604 ms 4000 KB Output is correct
25 Correct 1635 ms 3968 KB Output is correct
26 Execution timed out 2078 ms 9504 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2124 KB Output is correct
2 Correct 34 ms 1984 KB Output is correct
3 Correct 41 ms 2092 KB Output is correct
4 Correct 44 ms 2124 KB Output is correct
5 Correct 50 ms 2124 KB Output is correct
6 Correct 114 ms 2848 KB Output is correct
7 Correct 109 ms 2760 KB Output is correct
8 Correct 109 ms 2748 KB Output is correct
9 Correct 112 ms 2796 KB Output is correct
10 Correct 108 ms 2792 KB Output is correct
11 Correct 53 ms 2396 KB Output is correct
12 Correct 35 ms 1996 KB Output is correct
13 Correct 43 ms 2108 KB Output is correct
14 Correct 42 ms 2060 KB Output is correct
15 Correct 50 ms 2124 KB Output is correct
16 Correct 23 ms 1524 KB Output is correct
17 Correct 19 ms 1492 KB Output is correct
18 Correct 20 ms 1532 KB Output is correct
19 Correct 19 ms 1524 KB Output is correct
20 Correct 24 ms 1580 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 4 ms 1240 KB Output is correct
3 Correct 3 ms 1240 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 4 ms 1240 KB Output is correct
7 Correct 4 ms 1244 KB Output is correct
8 Correct 3 ms 1196 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 4 ms 1244 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 3 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 3 ms 1116 KB Output is correct
18 Correct 2 ms 1112 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 1798 ms 4056 KB Output is correct
22 Correct 1645 ms 4016 KB Output is correct
23 Correct 1427 ms 3524 KB Output is correct
24 Correct 1604 ms 4000 KB Output is correct
25 Correct 1635 ms 3968 KB Output is correct
26 Execution timed out 2078 ms 9504 KB Time limit exceeded
27 Halted 0 ms 0 KB -