oj.uz

Submission #801982

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

  Mint ret = 1;
  for (int i = n; i > n - k; --i)
    ret *= i;
  ret *= invFact[k];
  return 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);

  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;
  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<Mint> revProd(nbEcoles + 1);
    int szInt = up - lo + 1;
    revProd[0] = 1;
    for (int i = 0; i < nbEcoles; ++i)
      revProd[i + 1] = revProd[i] * (szInt - i);
    auto calc = [&](int szInt, int cntMiddle, bool midDiff) {
      Mint ret = 0;
      for (int takeMiddle = 0; takeMiddle <= cntMiddle; ++takeMiddle)
        if (szInt >= takeMiddle + 1 + midDiff)
          ret += revProd[takeMiddle + 1 + midDiff] *
                 invFact[takeMiddle + 1 + midDiff] *
                 binom(cntMiddle, takeMiddle);
      precalc[cntMiddle][midDiff] = ret;
    };

    for (int cntMiddle = 0; cntMiddle < nbEcoles; ++cntMiddle)
      for (int midDiff : {0, 1})
        calc(szInt, 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 1280 KB Output is correct
2 Correct 1259 ms 1272 KB Output is correct
3 Correct 1278 ms 1276 KB Output is correct
4 Correct 1284 ms 1280 KB Output is correct
5 Correct 1240 ms 1280 KB Output is correct
6 Correct 1266 ms 1272 KB Output is correct
7 Correct 1297 ms 1272 KB Output is correct
8 Correct 1276 ms 1280 KB Output is correct
9 Correct 1295 ms 1276 KB Output is correct
10 Correct 1279 ms 1280 KB Output is correct
11 Correct 1306 ms 1276 KB Output is correct
12 Correct 1269 ms 1280 KB Output is correct
13 Correct 1307 ms 1276 KB Output is correct
14 Correct 1320 ms 1276 KB Output is correct
15 Correct 1566 ms 1296 KB Output is correct
16 Correct 324 ms 1156 KB Output is correct
17 Correct 302 ms 1160 KB Output is correct
18 Correct 241 ms 1164 KB Output is correct
19 Correct 244 ms 1168 KB Output is correct
20 Correct 259 ms 1160 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 1280 KB Output is correct
2 Correct 1259 ms 1272 KB Output is correct
3 Correct 1278 ms 1276 KB Output is correct
4 Correct 1284 ms 1280 KB Output is correct
5 Correct 1240 ms 1280 KB Output is correct
6 Correct 1266 ms 1272 KB Output is correct
7 Correct 1297 ms 1272 KB Output is correct
8 Correct 1276 ms 1280 KB Output is correct
9 Correct 1295 ms 1276 KB Output is correct
10 Correct 1279 ms 1280 KB Output is correct
11 Correct 1306 ms 1276 KB Output is correct
12 Correct 1269 ms 1280 KB Output is correct
13 Correct 1307 ms 1276 KB Output is correct
14 Correct 1320 ms 1276 KB Output is correct
15 Correct 1566 ms 1296 KB Output is correct
16 Correct 324 ms 1156 KB Output is correct
17 Correct 302 ms 1160 KB Output is correct
18 Correct 241 ms 1164 KB Output is correct
19 Correct 244 ms 1168 KB Output is correct
20 Correct 259 ms 1160 KB Output is correct
21 Correct 714 ms 1340 KB Output is correct
22 Correct 590 ms 1428 KB Output is correct
23 Correct 562 ms 1424 KB Output is correct
24 Correct 571 ms 1316 KB Output is correct
25 Correct 643 ms 1336 KB Output is correct
26 Correct 670 ms 1340 KB Output is correct
27 Correct 664 ms 1428 KB Output is correct
28 Correct 693 ms 1344 KB Output is correct
29 Correct 689 ms 1344 KB Output is correct
30 Correct 1334 ms 1324 KB Output is correct
31 Correct 1381 ms 1324 KB Output is correct
32 Correct 1359 ms 1324 KB Output is correct
33 Correct 1346 ms 1324 KB Output is correct
34 Correct 1330 ms 1320 KB Output is correct
35 Correct 1196 ms 1272 KB Output is correct
36 Correct 1244 ms 1272 KB Output is correct
37 Correct 1217 ms 1268 KB Output is correct
38 Correct 1218 ms 1276 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1160 KB Output is correct
2 Correct 22 ms 1160 KB Output is correct
3 Correct 22 ms 1156 KB Output is correct
4 Correct 23 ms 1108 KB Output is correct
5 Correct 22 ms 1104 KB Output is correct
6 Correct 23 ms 1172 KB Output is correct
7 Correct 25 ms 1172 KB Output is correct
8 Correct 23 ms 1172 KB Output is correct
9 Correct 29 ms 1108 KB Output is correct
10 Correct 24 ms 1152 KB Output is correct
11 Correct 22 ms 1108 KB Output is correct
12 Correct 22 ms 1108 KB Output is correct
13 Correct 22 ms 1108 KB Output is correct
14 Correct 22 ms 1108 KB Output is correct
15 Correct 22 ms 1156 KB Output is correct
16 Correct 11 ms 1108 KB Output is correct
17 Correct 11 ms 1140 KB Output is correct
18 Correct 11 ms 1140 KB Output is correct
19 Correct 11 ms 1132 KB Output is correct
20 Correct 12 ms 1108 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 1280 KB Output is correct
2 Correct 1259 ms 1272 KB Output is correct
3 Correct 1278 ms 1276 KB Output is correct
4 Correct 1284 ms 1280 KB Output is correct
5 Correct 1240 ms 1280 KB Output is correct
6 Correct 1266 ms 1272 KB Output is correct
7 Correct 1297 ms 1272 KB Output is correct
8 Correct 1276 ms 1280 KB Output is correct
9 Correct 1295 ms 1276 KB Output is correct
10 Correct 1279 ms 1280 KB Output is correct
11 Correct 1306 ms 1276 KB Output is correct
12 Correct 1269 ms 1280 KB Output is correct
13 Correct 1307 ms 1276 KB Output is correct
14 Correct 1320 ms 1276 KB Output is correct
15 Correct 1566 ms 1296 KB Output is correct
16 Correct 324 ms 1156 KB Output is correct
17 Correct 302 ms 1160 KB Output is correct
18 Correct 241 ms 1164 KB Output is correct
19 Correct 244 ms 1168 KB Output is correct
20 Correct 259 ms 1160 KB Output is correct
21 Correct 714 ms 1340 KB Output is correct
22 Correct 590 ms 1428 KB Output is correct
23 Correct 562 ms 1424 KB Output is correct
24 Correct 571 ms 1316 KB Output is correct
25 Correct 643 ms 1336 KB Output is correct
26 Correct 670 ms 1340 KB Output is correct
27 Correct 664 ms 1428 KB Output is correct
28 Correct 693 ms 1344 KB Output is correct
29 Correct 689 ms 1344 KB Output is correct
30 Correct 1334 ms 1324 KB Output is correct
31 Correct 1381 ms 1324 KB Output is correct
32 Correct 1359 ms 1324 KB Output is correct
33 Correct 1346 ms 1324 KB Output is correct
34 Correct 1330 ms 1320 KB Output is correct
35 Correct 1196 ms 1272 KB Output is correct
36 Correct 1244 ms 1272 KB Output is correct
37 Correct 1217 ms 1268 KB Output is correct
38 Correct 1218 ms 1276 KB Output is correct
39 Correct 24 ms 1160 KB Output is correct
40 Correct 22 ms 1160 KB Output is correct
41 Correct 22 ms 1156 KB Output is correct
42 Correct 23 ms 1108 KB Output is correct
43 Correct 22 ms 1104 KB Output is correct
44 Correct 23 ms 1172 KB Output is correct
45 Correct 25 ms 1172 KB Output is correct
46 Correct 23 ms 1172 KB Output is correct
47 Correct 29 ms 1108 KB Output is correct
48 Correct 24 ms 1152 KB Output is correct
49 Correct 22 ms 1108 KB Output is correct
50 Correct 22 ms 1108 KB Output is correct
51 Correct 22 ms 1108 KB Output is correct
52 Correct 22 ms 1108 KB Output is correct
53 Correct 22 ms 1156 KB Output is correct
54 Correct 11 ms 1108 KB Output is correct
55 Correct 11 ms 1140 KB Output is correct
56 Correct 11 ms 1140 KB Output is correct
57 Correct 11 ms 1132 KB Output is correct
58 Correct 12 ms 1108 KB Output is correct
59 Execution timed out 2062 ms 1344 KB Time limit exceeded
60 Halted 0 ms 0 KB -